백준 1541번 : 잃어버린 괄호 (문제 따라가기)

하드코딩의 정석..은 무슨 아이디어 생각 안나면 맨날 이렇게 푸는거 같다. 훨씬 간단하고 짧게 풀 수 있는 방법은 항상 있으나, 왜인지 문제에서 제시하는 방향 그대로 따라가다보면 답이 나올거라 생각하고 구현하는 병에 걸린 것 같다.

---

import sys
input = sys.stdin.readline
import copy
info_next = list(map(str, input().rstrip()))    #   55-50+40
info = copy.deepcopy(info_next)     # 얕은 복사로 인한 데이터 변환을 막기 위함
idx = 0                             # idx를 증가시키며 순회


# 먼저 괄호가 들어가야할 위치를 생각해보면 음수 부호 뒤에 여는 괄호가 들어가고
# 다음 (-) 연산자가 나온다면 닫기 or 문자열이 끝났을 경우 임을 그리디하게 생각
while True:
    if info[idx] =='-':         # (-) 연산자 찾기
        info.insert(idx+1,'(')  # 찾았을 경우 괄호 열기
        for j in range(idx+1, len(info)):   # 이후 (-) 연산자가 있는지 탐색
            if info[j] == '-':              # 있다면 그 전에 괄호를 닫아줌
                info.insert(j,')')
                break           # 이후를 탐색할 필요 없으므로 break
        if info[-1] != ')':     # (-) 연산자가 발견되고 다음 (-)가 없을경우
            info.append(')')    # 연산식의 마지막에 괄호를 닫아줘야함
    idx += 1                    # 다음 인덱스 탐색
    judge = len(info)           # 반복문 종료조건으로 특이하게 넣어주는데 
    if idx == judge:            # 이유는 insert를 사용해 info배열 길이가 바뀌기 때문
        break
print(info)         #	['5', '5', '-', '(', '5', '0', '+', '4', '0', ')']

# 다음 과정은 떨어져있는 정수를 합치는 과정 (연산 전 처리 과정)
# 숫자가 나온다면 num에 합쳐주고 이후 연산자가 나오게 된다면 lst에 숫자를 담고 
# 연산자를 그뒤에 넣어준다.
lst = []
num = ''
for i in info:
    if i.isdigit():
        num += i
    elif i == '+':
        lst.append(num)
        num = ''
        lst.append('+')
    elif i == '-':
        if num:
            lst.append(num)
            num = ''
        lst.append('-')
    elif i == '(':
        lst.append('(')
    elif i == ')':
        lst.append(num)
        num = ''
        lst.append(')')
if num:             # 마지막 숫자 처리
    lst.append(num)
print(lst)          #   ['55', '-', '(', '50', '+', '40', ')']

# 이제 괄호 안의 연산을 먼저 진행해준다.
stack = []      # 계산 후 담길 리스트
stack_wait = [] # 계산 전 앞의 피연산자가 담겨있을 위치
judge = False   # 연산 스위치 on/off 버튼 괄호가 온다면 연산을 시작할 것
for i in lst:
    if i == '(' and judge == False: # 여는 괄호가 나오고 judge가 False면 스위치 on
        judge = True
    elif judge == False:            # 괄호가 아닌 것은 현재 연산 대상자가 아니기때문에 바로 stack에 담기
        stack.append(i)
    elif judge == True and i != ')': # 스위치 on 상태에서 여는 괄호가 아닌 것은 계산 전 위치에 넣어서 대기
        stack_wait.append(i)
    elif i == ')':                  # 닫는 괄호가 나온다면
        judge = False               # 스위치를 꺼주고
        stack_num = []              # 계산된 값 리스트
        stack_num_wait = []         # 괄호 안 연산이 여러개 일 수 있으므로 대기 리스트
        for j in stack_wait:        # 대기중인 스택 리스트 탐색
            if j.isdigit() and not stack_num_wait:  # 정수가 나오고 wait 리스트가 비어있다면
                stack_num.append(j)                 # 담아준다
            elif j == '+':                          # (+) 연산자가 나온다면
                stack_num_wait.append(j)            # 역시 wait 리스트에 담아준다
            elif j.isdigit() and stack_num_wait:    # 정수가 나오고 wait 리스트에 대기자가 있다면
                stack_num_wait.pop()                # 연산을 실행
                stack_num.append(str(int(stack_num.pop())+int(j)))  # 문자열이기 때문에 정수로 바꿔 연산
        stack.append(stack_num.pop())               # 모두 돌았을 때 최종 결과를 stack 리스트에 담아준다
print(stack)        #	['55', '-', '90']

# 이제 마지막 단계로 괄호 없는 연산들을 계산해주면 됨. 작동방식은 위와 동일
result = []
result_wait = []
for i in stack:
    if i.isdigit() and not result_wait:
        result.append(i)
    elif i == '+' or i == '-':
        result_wait.append(i)
    elif i.isdigit() and result_wait:
        if result_wait[0] == '+':
            result_wait.pop()
            result.append(int(result.pop())+int(i))
        elif result_wait[0] == '-':
            result_wait.pop()
            result.append(int(result.pop())-int(i))
print(*result)      #	-35      출력

---

 

출력을 한눈에 보면 나름... 멋있을 걸?

 

사실 위의 코드는 다듬을 부분이 굉장히 많다. 애초에 다시 풀었을때는 15줄로 끝냈다. 위 코드의 연산 일부를 간단하게 바꿀 수 있는데, input을 받을때 ' - ' 연산자를 기준으로 split 해주면 내 코드의 초기 분할과정과 재 결합을 할 이유가 없어진다. 또한 split으로 분할된 부분이 자동으로 괄호가 되었다고 생각할 수 있기 때문에 내 코드에서 마지막 부분 연산만 할 수 있다.

modify = input().split('-')
lst = []
print(modify)       #   ['55', '50+40']

for i in modify:
    cnt = 0
    arr = i.split('+')
    for j in arr:
        cnt += int(j)
    lst.append(cnt)

N = lst[0]          #   55

for i in range(1, len(lst)):
    N -= lst[i]

print(N)            #   -35

 

' - ' 연산자를 기준으로 나누고 순회 하면서 내부에 ' + ' 연산자가 있다면 계산 하고 마지막에 분할되어있는 요소들을 첫 정수에서(첫 정수는 무조건 0 이상 정수)이므로 빼주기만 하면 된다.

굉장히 간단한 것을 확인할 수 있다.

그래도 낭만 있었다. 한잔해!