백준/ Silver 3 문제 , 백준 Node.js 자바스크립트 1935 , 후위 표기식2 [자료구조, 스택]

백준/ Silver 3 문제 , 백준 Node.js 자바스크립트 1935 , 후위 표기식2 [자료구조]

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
자료구조 스택을 활용하는 문제.

 

 

문제 출처

https://www.acmicpc.net/problem/1935

1935번: 후위 표기식2

 

 

 

 

 

풀이

 

후위 표기식이라는 식을 푸는 문제이다.

 

우리가 흔히 사용하는 1+(2*3)=7 은 중위 표현식이고

 

이것을 후위 표현식으로 나타내면

 

123*+ 이렇게 나타낼 수 있겠다. 

 

이런 식을 풀면 된다.

 

 

https://todaycode.tistory.com/73

중위 표기법과 후위 표기법

 

후위 표기식에 대한 내용을 모른다면 위 블로그를 참조하자.

 

 

 

---

 

 

이 문제에서 핵심은

 

1. 알파벳에 해당하는 숫자를 식별하기.

 

2. 연산 순서 

 

이 부분이라 생각한다.

 

 

처음에 주어지는 Nums 배열에 담긴 숫자들은 각각 앞에서부터 A-Z 순서로 부여된다.

 

숫자가 [ 1, 2, 3 ] 이렇게 주어졌을때 후위표기식이 A+A+A 라면 1+2+3 이 아니고 1+1+1 이라는 점이다.

 

그렇다면 해당하는 알파벳에 맞는 숫자를 잘 저장해둬서 필요할때마다 뽑아 쓰는 편이 좋아보인다.

 

이럴때 바로 dict 를 사용하자.

 

어차피 숫자 앞에서부터 A 순서대로 이므로

 

초기 값을 아스키코드 65 로 설정한다. (아스키코드 65 번 = 'A' )

 

 

 

이런식으로 idx 에 65를 설정하고 알파벳으로 변환하여 주어지는 숫자의 길이만큼 for 문을 돌려서 

 

A부터 차례대로 숫자를 할당한다.

 

예를 들어 숫자가 [2, 4, 6, 8] 이 주어졌다면

 

 

dict 에는 { "A" = 2, "B" : 4, "C" : 6, "D" : 8} 이렇게 담기면 된다.

 

 

 

 

이후 후위 표기식을 앞에서부터 차례대로 확인한다.

 

이때 알파벳일 경우 dict 에 담긴 해당 숫자를 cal 이라는 배열에 담아주고,

 

부호가 일 경우 cal 에 담긴 끝에서부터 2개의 숫자를 부호를 사용해서 연산해주면 된다.

 

 

 

ABC*+DE/-

 

테스트케이스 1번을 확인해보면

 

 

이런식으로 후위표기식을 하나씩 확인해 나아가면서 cal 배열에 담거나 연산해 나아간다.

 

주의 할점은 연산을 할때는 연산을 한 값들은 다 빼주고 결과만 넣어줘야한다. 

 

 

이런식으로 계산을 하면 마지막에 cal 에는 최종 결과값 하나만 남아있을 것이다.

 

그 값을 이제 소수점 두자리 수 까지 맞춰서 출력하면 된다.

 

 

 

 

---

 

 

스택을 이용한 문제들은 접근하는 방법이 비슷하니 여러 문제들을 풀면 감이 금방 올것이다.

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/64061

프로그래머스

 

위 카카오 기출인 인형뽑기 문제도 스택을 이용하면 쉽게 풀 수 있다.

 

 

https://www.acmicpc.net/problem/9012

9012번: 괄호

 

이 문제도 연습하기 좋다.

 

 

 

 

 

 

 

정답

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

let [T, Arr, ...Nums] = input;
Nums = Nums.map((v) => Number(v));

function solution(T, Arr, Nums) {
  Arr = Arr.split("");
  let [cal, idx, result] = [[], 65, 0];
  let dict = {};
  for (let i = 0; i < Nums.length; i++) {
    dict[String.fromCharCode(idx)] = Nums[i];
    idx += 1;
  }
  Arr.map((v) => {
    if (/^[A-Z]*$/.test(v)) cal.push(dict[v]);
    else {
      let [a, b] = [cal.length - 2, cal.length - 1];
      if (v === "+") result = cal[a] + cal[b];
      else if (v === "-") result = cal[a] - cal[b];
      else if (v === "*") result = cal[a] * cal[b];
      else if (v === "/") result = cal[a] / cal[b];
      cal.pop();
      cal.pop();
      cal.push(result);
    }
  });
  return cal[0].toFixed(2);
}

console.log(solution(T, Arr, Nums));