[Gold II] 후위 표기식 - 1918

문제 링크

성능 요약

메모리: 30616 KB, 시간: 36 ms

분류

자료 구조(data_structures), 스택(stack)

문제 설명

수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다.

이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 이 방법의 장점은 다음과 같다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사용하면 순서를 적절히 조절하여 순서를 정해줄 수 있다. 또한 같은 방법으로 괄호 등도 필요 없게 된다. 예를 들어 a+b*c를 후위 표기식으로 바꾸면 abc*+가 된다.

중위 표기식을 후위 표기식으로 바꾸는 방법을 간단히 설명하면 이렇다. 우선 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다. 그런 다음에 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다.

예를 들어 a+b*c는 (a+(b*c))의 식과 같게 된다. 그 다음에 안에 있는 괄호의 연산자 *를 괄호 밖으로 꺼내게 되면 (a+bc*)가 된다. 마지막으로 또 +를 괄호의 오른쪽으로 고치면 abc*+가 되게 된다.

다른 예를 들어 그림으로 표현하면 A+B*C-D/E를 완전하게 괄호로 묶고 연산자를 이동시킬 장소를 표시하면 다음과 같이 된다.

결과: ABC*+DE/-

이러한 사실을 알고 중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하시오

입력

첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다.

출력

첫째 줄에 후위 표기식으로 바뀐 식을 출력하시오

풀이

expression = input()

stack = []
ans = ""
for s in expression:
    if s == '+' or s == '-':
        while stack and stack[-1] != '(':
            ans += stack.pop()
        stack.append(s)
    elif s == '*' or s == '/':
        while stack and (stack[-1] == '*' or stack[-1] == '/'):
            ans += stack.pop()
        stack.append(s)
    elif s == '(':
        stack.append(s)
    elif s == ')':
        while stack and stack[-1] != '(':
            ans += stack.pop()
        stack.pop()
    else:
        ans += s

while stack:
    ans += stack.pop()

print(ans)

배울점

분명히 전에 비슷한 문제를 풀었었던 기억이 있어서 금방 풀 줄 알았지만 해당 과정을 다시 기억하기가 너무 어려웠다. 아무래도 로직 자체는 구현하기 힘들지 않고 할 수 있었는데 왜 이 로직을 사용하면 중위 표기법이 후위 표기법으로 표현되는지 이해가 가지 않았기 때문에 기억에 남지 않는 것 같다.

로직은 간단하다.

1. 계산 기호 ( '+', '-', '/' , '*' , '(' , ')' ) 가 아닌 숫자나 문자일 경우 바로 출력한다.
2. 계산 기호일 경우, 자신보다 우선순위가 낮은 기호가 나올 때까지 빼서 출력한다.
3. '(' 기호는 우선순위가 제일 낮고 ')' 가 나올 시 '('가 나올 때까지 안에 있는 모든 기호들을 출력한다.
4. '(' 는 무조건 추가한다.

위의 로직들을 지키면서 해당 중위 표기법을 순회 및 출력하면 후위 표기법이 출력이 된다.

내가 해석한 로직의 의미는 다음과 같다.

1. 문자나 숫자일 경우는 순서가 바뀔 경우가 없기 때문에 그대로 출력한다.
2. 우선순위가 높은 기호가 더 빨리 출력이 돼야 하니 스택에 우선순위가 낮은 기호를 만나기 전까지 출력을 시킨다. 예를 들어 +는 *보다 일반적으로 늦게 출력이 되어야 하기 때문에 만약 스택에 먼저 *이 있을 경우 우선적으로 *를 출력한다.
3. ( ) 안에 있는 기호들은 내부적으로 2번 로직이 적용되면서 우선적으로 출력이 되어야 한다. 따라서 (를 우선순위를 제일 낮추어 2번 로직에 의해 (보다 먼저 있었던 기호들이 출력이 되는 것을 막고 )이 나왔을 때, (까지의 기호들이 출력되게 한다. 예를 들어 기호 스택이 ['+' , '*']가 저장 되어있다. ( 가 추가되면 앞에 기호들이 (이후로 오는 기호들보다 먼저 출력되면 안되기 때문에 (의 우선순위를 최하로 두어 막는다. 그 다음 기호들이 추가된 후, )가 추가되면, (까지의 기호들을 출력하게 된다.

로직 자체는 코드로 구현하기가 쉬워도 이에 대한 심도 있는 이해가 있지 않으면 금방 까먹는다는 것을 깨달았다. 한 문제를 풀더라도 확실히 이해하고 넘어가도록 하자.

다리를 지나는 트럭

문제 설명

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간	다리를 지난 트럭	다리를 건너는 트럭	대기 트럭
0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

입출력 예

bridge_length	weight	truck_weights	return
2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

from collections import deque

def solution(bridge_length, weight, truck_weights):
#     방법 1
    # from collections import deque
    # q = deque()
    # n = len(truck_weights)
    # k = 0 
    # for i in range(n):
    #     # 마지막 인덱스 검사    
    #     i += k
    #     if i == n - 1:
    #         break
    #     now_truck = truck_weights[i]
    #     total_weight = now_truck
    #     q.append(now_truck)
    #     while total_weight <= weight:
    #         k += 1
    #         next_truck = truck_weights[i + k]
    #         total_weight += next_truck    
    
      # 방법 2
    # result = bridge_length + 1
    # n = len(truck_weights)
    # for i in range(len(truck_weights) - 1):
    #     now_sum = truck_weights[i] + truck_weights[i + 1]
    #     if now_sum > weight :
    #         result += bridge_length
    #     else :
    #         result += 1         
    #         tmp_sum = []
    #         for k in range(bridge_length - 1):
    #             if i >= k :
    #                 tmp_sum.append(truck_weights[i - k])
    #         if sum(tmp_sum) > weight :
    #             while sum(tmp_sum) <= weight :
    #                 tmp_sum.pop(0)
    #                 result += 1
    
#     방법 3
	
    answer = 0
    truck_queue = deque(truck_weights)
    bridge_queue = deque([])
    time_table = []
    #print(bridge_queue)
    #print(truck_queue)


    while True:
        weight_sum = 0
		# 트럭이 다리를 모두 지나간 경우 종료 
        if not truck_queue:
            if not bridge_queue:
                break
                
        # 시간을 1 증가 시킨다. 뒤에 해도 상관없음      
        # bridge 리스트는 2차원 리스트로 구성 [해당 트럭의 무게, 해당 트럭의 현재 위치]
        answer += 1
        
        # 만약 해당 가장 오래된 트럭의 위치가 다리 길이 이상이면 pop해준다.
        if bridge_queue:
            if bridge_queue[0][1] >= bridge_length:
                bridge_queue.popleft()
		
        # 전체적으로 위치를 1만큼 앞으로
        if bridge_queue:
            for i in range(len(bridge_queue)):
                bridge_queue[i][1] += 1
                
		# 다리 위에 있는 트럭들의 무게 총합 구해서
        if bridge_queue:    
            for i in range(len(bridge_queue)):
                weight_sum += bridge_queue[i][0]
        # 남아있는 트럭이 있으면      
        if truck_queue:
            # 다리에 자리가 남아있고 현재 다리위 무게랑 새로운 트럭의 무게의 합이 다리가 견딜 수 있는 무게보다 작으면
            if len(bridge_queue)+1 <= bridge_length and (weight_sum+truck_queue[0]) <= weight:
                #print(len(bridge_queue)+1,weight_sum+truck_queue[0])
                # 대기중인 트럭에서 하나 뽑아서
                truck = truck_queue.popleft()
                # 다리에 올린다.
                bridge_queue.append([truck,1]) 

        #print(bridge_queue)
        #print(truck_queue)
    return answer
                
    answer = result
    return answer

배울점

처음에 queue를 이용해서 풀려고 하다가 왠지 큐를 이용하지 않고 리스트 계산만 잘하면 될 듯해서 풀다가 방법2로 넘어갔는데 일반적인 트럭지나기 테스트 케이스들은 통과했지만 중간에 하나만 지나 가야하는 경우 등을 계산하는 것이 힘들어서 결국 다시 다리와 트럭을 큐로 사용해서 풀었다. 아직까지 큐를 활용하는 방법이 익숙치 않아 더 정진해야겠다.