[BOJ][Python]1918 풀이

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

1918번: 후위 표기식

def f(equation):
    priority = {'+':1, '-':1,'*':2,'/':2,'(':0}
    stack = []
    for i in equation:
        if i.isalpha():
            print(i, end='')
        else:
            if len(stack) == 0 or i == '(':
                stack.append(i)
            elif i == ')':
                while True:
                    tmp = stack.pop()
                    if tmp == '(':
                        break
                    else:
                        print(tmp, end='')
            else:
                while True:
                    if len(stack) != 0 and priority[stack[-1]] >= priority[i]:
                        print(stack.pop(), end='')
                    else:
                        break
                stack.append(i)
    while stack:
        print(stack.pop(), end='')

equation = input()
f(equation)

사실 제 기준에서는 약간 어려웠습니다. 문자열을 조작하는 문제들을 나름대로 풀어봤었는데 그 중에서도 가장 고민을 많이 했던 것 같아요. 풀이랑은 크게 관련이 있진 않아서 적을지 말지 좀 고민을 했습니다만 일단은 적어보겠습니다. 관심이 없으신 분들은 토글을 건너뛰고 보시면 될 것 같아요.

저는 먼저 괄호 유무 체크, 곱셈 or 나눗셈 연산 유무 체크, 덧셈 or 뺄셈 연산 유무 체크의 총 3번의 반복문을 진행하도록 함수의 틀을 잡았습니다. 괄호도, 곱셈, 나눈셈도 없다면 덧셈과 뺄셈만 남으니까 그냥 선형 탐색을 하면서 순서대로 문자열 조작을 하면 되겠다는 생각이었어요.

 

그리고 괄호가 나오면 재귀 호출을 하는 방법을 생각했습니다. 인수로 괄호의 위치를 넘겨주어서 해당 위치에서 반복문을 시작하는거죠. 사실 이게 고민의 구렁텅이로 빠지는 방법이 아니었나 싶긴 하네요. 괄호가 입력으로 들어올 수 있는데 출력에는 괄호가 없어야 한다는 점에서 원본 문자열을 수정하는 방식을 가져간다면 원본 문자열의 인덱스를 활용하는 방법은 어떻게 써도 문제를 야기할 가능성이 높으니 애초에 다른 방법을 생각해야 했습니다. 뭐, 반성문 같은거니까 일단은 더 작성해보겠습니다.

 

그래서 괄호를 만나면 다시 재귀 호출을 할 것이고 없다면 연산자가 있는지 확인하고 우선순위에 따라 연산을 하는 방법을 생각했는데 단순하게 한 번만 연산하는거라면 문제가 없는데 A*B-C+A/D 뭐 이런식으로 연산이 연속해서 나왔을 때 처리할 방법이 좀 까다로웠습니다. 연산의 최소 단위(피연산자,연산자,피연산자)를 후위 표기로 바꾼 이후에는 해당 후위 표기식을 하나의 문자처럼 처리를 해야했습니다. 하지만 일단 합친다고 하면 기존에 그 자리에 있던 문자열들을 없애면서 원래 방정식의 길이에 변화가 생기고 인덱스를 인수로 넘기는 재귀 호출이 제대로 동작할 수 없게 됩니다. 그 외에도 괄호는 어떻게 없앨 건지, 문자열을 합치고나서 원래 문자열은 어떻게 할건지, pop을 써도 되겠지만 시간 복잡도는 어떻게 할건지, 전체 길이가 짧아지면서 생기는 반복문의 인덱스 에러는 어떻게 해결할 것인지... 사실 모든 문제의 근원이 인덱스가 되었습니다. 어떤 식으로 하더라도 인덱스를 인수로 사용하는 순간 문자열에 어떤 조작을 하는 것 자체가 불가능해진거죠.

 

결국 제 머리로는 좋은 방법을 못찾아서 검색을 좀 해봤는데 해당 문제는 컴퓨터 전공을 하신 분들은 자료구조 시간에 흔히들 풀어보는 스택의 응용 문제라고 하더라구요. 저는 컴퓨터 전공이 아니다보니 처음 보는 문제였고 그래서 공부를 좀 했습니다. 알고 보면 간단한데 혼자서는 떠올리기 좀 힘들지 않나 하는 생각이 들었네요.

해당 문제의 아이디어는 문자는 그냥 출력하고 연산자는 스택에 저장하되, 현재 저장하고자 하는 연산자의 바로 직전에 저장되어 있는 연산자가 더 우선순위가 높다면 스택에서 빼내어 출력하고 현재의 연산자를 저장합니다. 여는 괄호가 나올 경우는 그냥 저장했다가 나중에 닫는 괄호가 오면 여는 괄호가 나올 때 까지 전부 빼서 출력하는 방식으로 문제를 해결했네요.

 

사실 완벽하게 이론적으로 이해를 해서 이렇게 하는구나 라는 경지는 도달하지 못했고, 그냥 푼 걸 보니 이렇게 풀 수 밖에 없구나 라는 생각이 드는 정도라 개인적으로 만족스럽진 않습니다만, 이 문제에서 그치지 않고 어떻게 하면 앞으로 만날 다른 문제에 이 테크닉을 적용시켜볼 수 있을지는 고민해볼만한 사항인 것 같습니다. 사실 스택이나 큐나 후입선출이니, 선입선출이니 특징만 알고 그걸 그대로 활용만 했었지 우선순위를 정해놓고 우선순위에 따라 다른 조작을 하는 방식은 아직 생각해본 적이 없었던 것 같네요.