[백준] 20936 - 우선순위 계산기 (P4)

---

문제 소개

---

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

20936번: 우선순위 계산기

2021 WINTER 신촌 연합 대학생 프로그래밍 대회(SAUPC)의 A번으로 나왔던 문제이다.

당시에는 너무 복잡해서 그냥 넘겨버렸는데, 아니나 다를까 플레티넘 문제였다ㅋㅋ

 

이번 SAUPC에서 구현문제를 담당하게 되어서 연습을 위해 풀어보았다.

전에 풀었던 뒤집힌 계산기와 비슷한 유형이지만, 좀 더 복잡하다.

 

알고리즘을 어떤 걸 써야할지 감이 잡힐 듯 말듯 해서, 결국 알고리즘 분류를 보고 문제를 풀었다.

알고리즘 분류를 보니 혹시 이거 써야하나? 했던 것들이 죄다 들어가 있어서 놀랐다.

설마 이거 다 써야 했나 했는데 진짜 다 쓰게 됐다..

---

풀이 과정

---

우선 문제 설명과 조건을 보면, 입력은 하나의 문자열로 수식이 주어진다.

이 수식을 잘 파싱해서 숫자와 연산자로 분리한 다음, 문제에서 요구하는 방식으로 수식을 계산하면 된다.

 

전과 마찬가지로, 파싱에는 정규식을 사용했다.

숫자 앞에 의미없는 0이 붙어 있는 것은 문자열에 int 를 씌우면 알아서 해결된다.

 

문제는 그 다음인데, 매우 복잡하다.

계산순서가 다음과 같다.

 

1. 해당 연산만 놓고 봤을 때, 연산 결과 값이 가장 큰 것

2. 1번 값이 여러개면, 우선순위가 높은 연산자 (*, /)

3. 2번 값도 여러개면, 먼저 나온 연산자 (인덱스가 앞서는 것)

 

처음에는 나이브하게 모든 연산자를 다 돌아서 1번 조건에 해당하는 걸 찾고,

그걸 계산한다음, 그 값을 가지고 다시 주변의 연산자를 계산해서

다시한번 모든 연산자를 다 도는 걸 반복하는 방법을 생각했다.

 

이것도 꽤나 복잡하지만 구현하지 못할 건 아니다.

그런데 이런 방식으로 하면 절대 시간내에 풀 수가 없다.

 

주어진 수식의 길이가 최대 20만이다.

그럼 최악의 경우 연산자가 약 10만개가 있을 수 있는데,

위 알고리즘은 모든 연산자를 연산자의 수만큼 반복해서 탐색한다.

즉 O(N^2)의 시간복잡도를 갖기 때문에 반드시 시간이 초과된다.

못해도 O(NlogN)으로는 풀어야한다.

---

우선 생각해볼 점은 연산자를 하나 골라서 그 결과값을 구해도,

그 결과값이 미치는 영향은 자기 양옆의 연산자 2개가 끝이다.

즉 전체의 연산 순위로 보면 대체로 순위 변화가 없다.

따라서 이미 계산해놓은 연산 순위를 다시 계산할 필요는 없다.

 

하지만 대체로 순위 변화가 없다는 것이지, 순위는 변하므로,

변한 순위를 반영해서 새로운 연산자를 추출해야한다.

 

이 문제를 해결하는데는 '우선순위 큐' 만큼 좋은 자료구조가 없다.

저 1, 2, 3 조건을 담기 위해 나는 우선순위 큐에 다음과 같이 자료를 넣었다.

 

( - 연산 결과 값, ( *, / 면 -1 아니면 0 ), 연산자 인덱스 )

파이썬의 heapq 모듈의 우선순위큐는 최소힙이라서 항상 작은 값을 뽑아준다.

그래서 우선 순위가 높은 걸 먼저 뽑을 땐 - 를 붙여서 저장해준다.

 

이제 연산자를 차례대로 뽑는 것은 해결했다.

하지만 아직 문제는 남아있다.

---

연산자를 뽑아서 계산을 하면, 그 계산 결과를 양 옆의 연산자의 피연산자로 반영해야한다.

제일 간단한 것은 그냥 수식을 리스트로 저장해놓고, 계산하는 것이겠지만,

이 문제는 지난번 계산기 문제와 다르게 수식을 계산할 때 스택을 써서 풀 수 없다.

 

연산자를 고르는 순서가 뒤죽박죽이기 때문에, 리스트를 썼다간

중간에 원소를 삭제하고나서 리스트를 정렬하느라 많은 시간을 잡아먹고 시간초과가 발생한다.

그래서 중간에 삽입과 삭제가 용이한 연결리스트, 그 중에서도 이중 연결 리스트를 사용한다.

 

이때 저장해야할 정보가 좀 많다.

1. 내 왼쪽 피연산자

2. 내 오른쪽 피 연산자

 

다른 연산에 의해 내 피연산자가 바뀔 수 있기 때문에 우선 이 둘이 저장되어야 한다.

또 다른 연산이 진행되면 해당 연산자는 빠지면서 연산자 순서도 바뀐다.

따라서

 

3. 내 왼쪽 연산자

4. 내 오른쪽 연산자

 

이 정보도 저장해야한다.

 

그리고 이 이중 연결리스트의 구현은 맵(딕셔너리)으로 해야한다.

이중 연결리스트의 특징이 중간에 삽입 삭제가 용이하다는 것인데, 리스트로 구현할 수는 없다.

---

여기까지 왔다면 이제 거의 다 됐다.

이제 상기한 자료구조를 가지고 알고리즘을 짜보자.

내가 문제를 푼 순서는 다음과 같다.

 

0. 정답의 초기 값을 수식의 맨 처음 숫자로 설정한다.

수식으로 숫자 하나만 입력으로 들어온다면 우선순위 큐에 데이터가 없기 때문에

이 값을 바로 출력하게 된다.

 

1. 수식을 왼쪽부터 순서대로 훑으면서 연결리스트를 작성하고 우선순위 큐에 데이터를 넣는다.

 

<우선순위 큐에 데이터가 있는 동안 반복>

2. 우선순위 큐에서 데이터를 꺼낸다.

 

3. 데이터가 갖고있는 '연산 결과 값'과 연결리스트에 저장된 '연산 결과 값'을 비교한다.

다른 연산에 의해 내 피연산자가 바뀌면,

전에 넣었던 '연산결과 값'과 현재의 '연산 결과 값'이 일치하지 않을 수도 있다.

 

4-1. 비교값이 일치하지 않으면 그 값은 버리고 우선 순위 큐에서 새로 뽑는다.

4-2. 비교값이 일치하면, 정답을 해당 값으로 바꾼다.

어차피 마지막 '최후의 연산'이 정답이 되기때문에, 매 연산으로 정답을 갱신해도 괜찮다.

 

5. 내 왼쪽 연산자의 오른쪽 연산자를 내 오른쪽 연산자로 설정한다.

내 왼쪽 연산자의 오른쪽 피연산자를 계산한 '연산 결과 값'으로 설정한다.

(이 두 과정은 연결리스트에 대해 진행한다.)

내 왼쪽 연산자에 대해 다시 연산을 진행해서 그 값을 기준으로 데이터를 만들어

우선순위 큐에 해당 연산자 데이터를 새로 넣는다.

 

6. 오른쪽에 대해서도 위 과정을 수행한다.

<여기까지의 과정을 반복>

 

7. 저장한 정답 값을 출력한다.

---

정답 코드

---

import sys
import re
import heapq
input = sys.stdin.readline

exp = input().rstrip()
nums = list(map(int, re.split(r'\*|/|\+|-', exp)))
oper = list(re.sub(r'[0-9]', '', exp))

answer = nums[0]
pq = []
oper_info = dict()
for i in range(1, len(nums)):
    # 연산자 정보 (좌, 우 숫자, 자신의 연산기호, 내 왼쪽의 연산자 번호, 내 오른쪽의 연산자 번호) 저장
    oper_info[i-1] = ([nums[i-1], nums[i], oper[i-1], i-2, i])

    # 우선순위 큐에 저장할 연산결과값, 연산자 우선순위, 인덱스 계산
    oper_prior = -1 if oper[i-1] == '*' or oper[i-1] == '/' else 0
    if oper[i-1] == '*':
        value = nums[i-1] * nums[i]
    elif oper[i-1] == '/':
        value = nums[i-1] // nums[i]
    elif oper[i-1] == '+':
        value = nums[i-1] + nums[i]
    elif oper[i-1] == '-':
        value = nums[i-1] - nums[i]
    else:
        raise Exception("wrong operator")

    heapq.heappush(pq, (-value, oper_prior, i-1))


def checkValue(index):
    if oper_info[index][2] == '+':
        return oper_info[index][0] + oper_info[index][1]
    elif oper_info[index][2] == '-':
        return oper_info[index][0] - oper_info[index][1]
    elif oper_info[index][2] == '*':
        return oper_info[index][0] * oper_info[index][1]
    else:
        ### 음수에 대한 몫 계산 처리 필요
        return oper_info[index][0] // oper_info[index][1]

while pq:
    get_value, prior, index = heapq.heappop(pq)

    # 현재 연산자 정보의 값과 pq 값이 일치하면, 최신 값을 꺼낸 것으로 본다. (검증 필요, 값이 겹칠 수 있으므로)
    check_value = checkValue(index)
    if -get_value == check_value:
        answer = check_value

        left_oper = oper_info[index][3]
        right_oper = oper_info[index][4]

        # 내 왼쪽 연산자에 대해
        if left_oper > -1:
            # 오른쪽 피연산자를 결과값으로 바꿔준다.
            oper_info[left_oper][1] = check_value
            # 오른쪽으로 연결된 연산자를 내 오른쪽 연산자로 바꿔준다.
            oper_info[left_oper][4] = right_oper
            # 바꾼 피연산자로 계산한 값을 pq에 넣어준다.
            left_change_value = checkValue(left_oper)
            if oper_info[left_oper][2] == '*' or oper_info[left_oper][2] == '/':
                left_operator = -1
            else:
                left_operator = 0
            heapq.heappush(pq, (-left_change_value, left_operator, left_oper))

        # 내 오른쪽 연산자에 대해
        if right_oper < len(oper_info):
            # 왼쪽 피연산자를 결과값으로 바꿔준다.
            oper_info[right_oper][0] = check_value
            # 왼쪽으로 연결된 연산자를 내 왼쪽 연산자로 바꿔준다.
            oper_info[right_oper][3] = left_oper
            # 바꾼 피연산자로 계산한 값을 pq에 넣어준다.
            right_change_value = checkValue(right_oper)
            if oper_info[right_oper][2] == '*' or oper_info[right_oper][2] == '/':
                right_operator = -1
            else:
                right_operator = 0
            heapq.heappush(pq, (-right_change_value, right_operator, right_oper))

print(answer)

---

생각보다 엄청 복잡해서 머리를 싸매면서 풀었네요..

이런 문제는 꼭 주석을 활용해 생각을 정리해가며 풀어야 헷갈리지 않고 실수도 줄어드는 것 같습니다.

그래도 풀이 과정을 떠올리는 과정이 복잡한 것에 비해 구현 난이도는 비교적 쉬웠던 것 같습니다.

여러 자료구조와 엮어서 개인적으로 참 잘 만든 문제같다는 생각이 듭니다.

 

(근데 지금보니 몫 연산에 음수 부분 예외 케이스를 안두었는데 맞았네요..

연산 중간에 피연산자 한쪽에만 음수가 발생하는 케이스가 테케중에 없나봅니다..)