백준 1935번 Pseudo code

문제 링크

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

1935번: 후위 표기식2

 

시간 제한 / 메모리 제한

2 초

128 MB

 

문제

후위 표기식과 각 피연산자에 대응하는 값들이 주어져 있을 때, 그 식을 계산하는 프로그램을 작성하시오.

 

입력

첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이는 100을 넘지 않는다) 그리고 셋째 줄부터 N+2번째 줄까지는 각 피연산자에 대응하는 값이 주어진다. 3번째 줄에는 A에 해당하는 값, 4번째 줄에는 B에 해당하는값 , 5번째 줄에는 C ...이 주어진다, 그리고 피연산자에 대응 하는 값은 100보다 작거나 같은 자연수이다.

후위 표기식을 앞에서부터 계산했을 때, 식의 결과와 중간 결과가 -20억보다 크거나 같고, 20억보다 작거나 같은 입력만 주어진다.

출력

계산 결과를 소숫점 둘째 자리까지 출력한다.

예제 입력

5
ABC*+DE/-
1
2
3
4
5

예제 출력

6.20

 

문제 풀이를 위해 생각한 것

1. 중위표기식을 후위표기식으로 만드는 데 스택을 사용한다.
2. 스택으로 후위표기식을 사칙연산 할 수 있다.
3. 영대문자 A~N번째 알파벳까지 순서대로 입력을 받아, map 자료구조로 둘을 mapping한다.

 

사용한 자료구조

스택, 맵.

후위표기식을 사칙연산할 때는 스택, A~Z를 숫자와 대응시킬 때는 맵 자료구조 활용

 

풀이 코드

n = 첫 입렧값을 정수로
postfix = 입력값을 배열의 형태로 저장
map = 맵 자료구조 선언
stk = 스택 자료구조 선언

97(A)부터 n개의 입력 i 동안:
	map[ord(i)] = 입력값을 정수로 변환하여 mapping

postfix 배열의 원소 p에 대하여:
	if isdecimal(p): # 십진수이면 stk에 push
		stk.push(p)
	if p in (+, -, *, /): # 부호이면 두 개의 값을 pop해서 사칙연산 수행
		second = map[stk.pop()] # 대응 값 적용
		first = map[stk.pop()]
		stk.push(first p second) # 사칙연산

print stk.pop() #최종 결과 값 출력

 

시간 복잡도 분석

O(N).

스택의 삽입, 삭제 연산과 맵의 삽입, 조회 연산은 O(1)의 시간 복잡도를 가짐.

따라서 N개의 원소에 대하여 O(1)의 연산을 수행하고, 이는 O(N)의 시간 복잡도를 가진다.

 

문제에서 중요한 부분

맵 자료구조와 스택을 함께 사용해서 삽입, 삭제, 조회, 사칙연산 모두 O(1)의 시간 복잡도로 수행할 수 있었고, 이는 시간 복잡도를 줄이는 데 중요했다.

만약 이를 코드로 구현할 때면, 사칙연산 부호와 정수에 대해 type을 언제 어떻게 변환해야 할 지 고민해봐야 한다.

 

참고자료

https://todaycode.tistory.com/73?category=997273 

중위 표기법과 후위 표기법