[python] 백준 2504 - 괄호의 값

출처 : 백준, https://www.acmicpc.net/problem/2504

2504번: 괄호의 값

 

 

풀이

 

def solution(pars):
  open = ['(', '[']
  close = [']', ')']
  stack = []
  
  prev_p = ''
  eq = ''
  
  for p in pars:
    if p in open:
      if prev_p in open: # 3. 열림-열림일 경우 : 식에 ( 괄호 추가
        eq += '('
      elif prev_p in close: # 5. 닫힘-열림일 경우 : 식에 + 추가
        eq += '+'
        
      stack.append(p) # 1. 열림 괄호일 경우 : stack에 추가
    else:
      #잘못된 괄호식일 경우 return 0
      if not stack or p == ']' and stack[-1] == '(' or p == ')' and stack[-1] == '[':
        return 0
      
      if prev_p in close: # 4. 닫힘-닫힘일 경우 : 식에 ) 괄호 추가, * 추가
        eq += ')'
        eq += '*'
        
      pop_p = stack.pop() # 2. 닫힘 괄호일 경우 : stack에서 꺼내서 숫자 추가
      
      if pop_p == '(':
        eq += '2'
      else:
        eq += '3'

    prev_p = p

  #잘못된 괄호일 경우 return 0 아니면 계산값 return
  return eval(eq) if not stack else 0 

if __name__ == '__main__':
  pars = input()

  print(solution(pars))

 

1. 열림 괄호일 경우 : stack에 추가

2. 닫힘 괄호일 경우 : stack에서 꺼내서 매칭 숫자를 식에 추가

3. 열림-열림일 경우 : 식에 ( 괄호 추가

4. 닫힘-닫힘일 경우 : 식에 ) 괄호 추가, *추가

5. 닫힘-열림일 경우 : 식에 + 추가

 

라는 규칙을 발견했고 두 괄호 사이의 관계를 판별하는 것이 단독 괄호에 대한 처리보다 먼저 와야함을 발견했다.

이를 코드화 한 것이 위의 코드이다.

---

 

시간 복잡도

 

O(n)

 

다른 사람의 풀이를 보면서 알게 된 점

 

-

 

고찰

 

stack 사용 시 Index Error가 날 수 있는 대표적인 경우 2가지

 

1. stack[-1]과 같이 stack의 성분에 직접적으로 접근하는 경우

2. stack에 넣었다 뺐다 하는 경우 모든 순회 후 마지막에 stack이 다 비워지지 않은 경우

 

2번의 경우는 stack을 쓸 때 stack이 비워져야 정상 입력임을 판별할 경우에 주로 사용한다.

stack 사용 시 이 2가지 경우에 대해서는 필요시 미리 처리하고 들어가면 좋음.

나중에 까먹어서 찾느라 고생하기 때문.