먹고 기도하고 코딩하라

[백준] 2504 : 괄호의 값 (파이썬) 본문

자료구조&알고리즘/BOJ

[백준] 2504 : 괄호의 값 (파이썬)

2G Dev 2022. 1. 10. 13:30
728x90
728x90

 

 

2504번: 괄호의 값

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.  만일

www.acmicpc.net

 

보통 괄호 짝이 맞는지 확인하고 계산하는 문제는 스택을 써서 푸는 문제다. 이 문제 역시 스택을 사용하는 문제는 맞지만, 다른 점이라면 소괄호와 대괄호가 섞여있으며 괄호가 홑겹인지 여러 겹인지에 따라 그 값을 더하는지 곱하는지가 달라진다는 것이다.

얼핏 보기에는 그렇게 어려운 문제는 아닌 것 같아 보이는데 값을 계산하는 게 되게 까다롭다. 

 

우선 내가 생각한 것들.

입력을 고려했을 때 sys.stdin.readline을 쓰지 않고 그냥 input을 써도 될 것 같은 문제. 실제로 input으로 받아도 시간 초과가 나지 않았다.
규칙 1. 여는 괄호 (, [라면 스택에 단순히 push한다.
규칙 2. 닫는 괄호 )일 때, 스택의 top에 있는 것이 [이거나 스택이 비었다면 에러. 바로 중단한다. 마찬가지로 닫는 괄호 ]일 때, 스택의 top에 있는 것이 (이거나 스택이 비었다면 에러이므로 바로 중단한다.
여기까지는 생각했지만, 값을 어디에 저장하고 계산해야 할지가 난관이었다.
그래서 20분 정도 고민하다가 결국 블로그에 풀이를 찾아봤다.

 

정리된 풀이는 다음과 같다.

규칙 1에서 여는 괄호를 스택에 넣을 때, 그냥 push만 할 것이 아니라 해당 괄호에 해당하는 값을 temp에 곱한다. 이 때, 이 temp의 초기값은 1이어야 한다. 0으로 하면 곱해봤자 0이므로 꼭 1로 초기화해야 한다.
규칙 2에서 닫는 괄호가 나올 때, 지금 검사하는 것의 이전 인덱스의 괄호가 짝이 맞아서 쌍을 이루는 괄호라면 temp를 최종 결과인 res에 더한다. 그 후 temp를 해당 괄호에 해당하는 값으로 나눈 뒤, 괄호를 계산한 셈이므로 pop하면 된다.
최종적으로는 res가 답이 된다. 
또 하나, for문을 돌릴 때 for-in이 아니라 전체 입력 s의 길이만큼 range 객체를 만들어야 한다. 그래야 이전 위치의 괄호와 현재 괄호를 비교할 수 있기 때문이다. 나는 처음에 그걸 모르고 for in 으로 했다가 통째로 고쳤다.

 

완성된 정답 코드

s = input()
stack = []
tmp = 1
res = 0

# for c in s를 하면 안 되고 길이로 돌아야 함
for i in range(len(s)):
  if s[i] == '(':
    tmp *= 2
    stack.append(s[i])
  elif s[i] == '[':
    tmp *= 3
    stack.append(s[i])

  elif s[i] == ')':
    if not stack or stack[-1] == '[':
      res = 0
      break
    if s[i-1] == '(':
      res += tmp
    tmp //= 2
    stack.pop() # pop도 까먹지 말고 꼭
  
  else:
    if not stack or stack[-1] == '(':
      res = 0
      break
    # [()]의 경우 ] 직전 문자가 )이므로 더하지 않고 넘어감
    # 단, 이 경우는 오류는 아님
    if s[i-1] == '[':
      res += tmp
    tmp //= 3
    stack.pop() # pop 까먹지 말기

if stack:
  res = 0
print(res)

다음에 이 문제를 또 풀었을 때 맞출 수 있을까? 까다로운 문제이고 닫는 괄호가 나올 때 어떻게 처리할 것인지 원리를 아는 게 더 중요할 것 같은 문제다.

 

 

728x90
반응형
1 Comments
댓글쓰기 폼