[BOJ] [python] 2504: 괄호의 값

Idea

입력 문자열을 왼쪽부터 읽어나간다.

• arr: 입력 문자열
• stack: 계산을 위해 문자열의 문자 하나하나를 append혹은 pop한다.
• tmp: 현재 계산중인 값
• answer: 최종 답

열린 괄호 (,[ 는 스택에 append하고 닫힌 괄호 ),] 는 pop을 진행한다.

( 를 만나면 tmp에 2를 곱하고 [ 를 만나면 tmp에 3을 곱한다.

현재 진행중인 곱하기 과정이 끝나면 tmp값을 answer에 더하고 tmp를 2 혹은 3으로 나눈다. 

 

트러블슈팅1: pop타이밍

arr = input()
stack = []
tmp=1
answer=0

for i in range(len(arr)):
  if arr[i] =='(':
    stack.append(arr[i])
    tmp*=2
    # print(tmp)
  elif arr[i] =='[':
    stack.append(arr[i])
    tmp*=3
    # print(tmp)
  elif arr[i]==')':
    j=stack.pop()
    # if len(stack)==0:
    #   answer+=tmp
    #   tmp=1 #확인 
    if arr[i-1]=='(':
      answer+=tmp
      # print("answer1:", answer)
    tmp//=2
    # print(tmp)
    if j!='(':
      answer=0
      tmp=1
      break
    # tmp//=2
  elif arr[i]==']':
    j=stack.pop()
    # if len(stack)==0:
    #   answer+=tmp
    #   tmp=1
    if arr[i-1]=='[':
      answer+=tmp
      # print("answer2: ",answer)
    tmp//=3
    # print(tmp)
    if j!='[':
      answer=0
      tmp=1
      break
    # tmp//=3
  
# if tmp!=1:
#   answer+=tmp
print(answer)

초반 코드라 좀 더럽고 주석도 많다.

질문 게시판에서 반례 찾아왔다.

닫힌 괄호를 만나면 바로 스택에서 pop을 해 온 뒤 결과를 분기했는데

해당 반례에서는 첫번째 []괄호가 이미 pop돼서 스택에 아무것도 없는 상태로 ] 때문에 다시 pop이 되므로 인덱스에러가 발생하였다.

 

원래 닫힌괄호를 만나자마자 pop을 했는데 먼저 stack가 isempty인지 확인하고 pop을 시켰다.

stack이 비었다면 break

 

트러블슈팅2: 열린괄호가 여러개일 때

36%쯤에서 오답이 나왔다.

백준 질문게시판은..정말 세상의 모든 반례를 다 찾을 수 있을 것 같다는 생각이 든다.

닫힌괄호를 만나고 스택이 비어있지 않을 때 pop을 한다.

정상 괄호일 때는 괄호쌍에 맞는 열린 괄호가 나와야 한다는 상황만 처리했다.

 

계산이 다 끝나면 원래 스택이 비어야하지만 스택이 차있는 예외가 있었다.

 

최종 코드

arr = input()
stack = []
tmp=1
answer=0

for i in range(len(arr)):
  if arr[i] =='(':
    stack.append(arr[i])
    tmp*=2
  elif arr[i] =='[':
    stack.append(arr[i])
    tmp*=3
  elif arr[i]==')':
    if len(stack)==0:
      answer=0
      break
    j=stack.pop()
    if arr[i-1]=='(':
      answer+=tmp
    tmp//=2
    if j!='(':
      answer=0
      tmp=1
      break
  elif arr[i]==']':
    if len(stack)==0:
      answer=0
      break
    j=stack.pop()
    if arr[i-1]=='[':
      answer+=tmp
    tmp//=3
    if j!='[':
      answer=0
      tmp=1
      break
  
if len(stack)!=0:
  answer=0
print(answer)

 

예외 상황 처리에만 집중해서 그닥 예쁜 코드를 만들어내지는 못한 것 같다.

아직 나는 어떤 상황에서 어떤 자료구조를 왜 사용하는 지에 대한 이해가 부족하다고 느껴진다.

이번 문제도 다른 분들의 코드를 많이 참고하며 풀어나갔다.

 

그리고 상황을 나누고 예외를 생각하는 훈련이 많이 필요할 것 같다.