[백준/약점체크] 2504번: 괄호의 값

[문제]

 

[내 코드]

- 위 문제를 풀기 위해서는 먼저 괄호의 쌍이 올바르게 맞춰져 있는지 판단할 수 있어야 한다. 그 부분 코드 구현을 먼저 연습했다.

- 이 문제를 해결하기 위해서는 stack을 활용해야 한다

- list로 구현한 stack에 여는 괄호를 append하고 닫는 괄호가 나오면 후입선출한다 (stack.pop(-1))

- 만약 추출할 괄호가 없거나(stack == []), 추출한 괄호가 맞지(bd == match[d]) 않으면 쌍이 잘못 맞춰져 있다고 판단한다

data = list(map(str, input()))
match = {')':'(',
         ']':'['}
         
stack = []
result = 1
for d in data:
    if d in match.values():
        stack.append(d)
    else:
        if stack == []:
            result = 0
            break
        bd = stack.pop(-1)
        if bd == match[d]:
            result = 1
        else:
            result = 0
            
print(result)

 

그 다음 문제에서 요구하는 연산을 구현해야 한다

.. 몇시간 삽질한 끝에 정답을 찾아보며 이해했다

 

 

[정답]

 

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

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()
  
  else:
    if not stack or stack[-1] == '(':
      res = 0
      break
    if s[i-1] == '[':
      res += tmp
    tmp //= 3
    stack.pop()

if stack:
  res = 0
print(res)

 

- 곱셈의 분배법칙을 생각하면 되는데, 

괄호가 열릴 때 tmp를 미리 곱해주고, 괄호가 종료되면 tmp에서 해당되는 수만큼 나눠서 초기화시켜주는 것이다

 

예를 들어 

 

([]())

라는 예제를 생각해보면, 3과 2를 먼저 더하고 2를 곱할 생각을 하게 되는데

위 코드는 2*3 + 2*2 으로 접근하게 된다

 

iteration으로 보자면

1. s 가 열린괄호 ( 이므로 temp = 1(초기값)*2 = 2

2. s 가 열린괄호 [ 이므로 temp = 2(이전 temp값)*3 = 6

3. s 가 닫힌괄호 ] 이고, stack의 직전이 열린괄호 [ 였으므로 res = 0(초기화값) + 6(이전 temp값) = 6, 그리고 []가 닫혔으므로 temp 에서 3을 나눠 되돌린다 temp = 6 // 3 = 2

4. s가 열린괄호 ( 이므로 temp = 2 * 2 = 4

5. s가 닫힌괄호 ) 이고, stack의 직전이 열린괄호 ( 였으므로 res = 6 + 4 = 10, 그리고 ()가 닫혔으므로 temp 에서 2를 나눠 되돌린다 temp = 4 // 2 = 2

6. s가 닫힌괄호 ) 인데, stack의 직전이 열린괄호 ( 가 아니었으므로 temp 에서 2를 나눠 종료한다 temp = 2 // 2 = 1

 

코드를 보고 이해하는 데도 시간이 오래 걸린 문제였다... ㅜㅠ 

여러번 다시 보고 또 봐야겠다

 

 

아, 재귀를 활용한 코드도 봤다 (개인적으로 취향저격)

괄호가 열릴 때마다 재귀함수를 호출하는 아이디어까지는 생각했는데 이걸 구현한 코드를 보니 속이 다 후련함

- 리스트를 거꾸로 받아서 뒤에서부터 요소를 빼 쓴다

- 열리면 재귀함수를 호출하고 값들을 다 더해주는데, 닫히면 곱하면서 return 한다

 

import sys
input = sys.stdin.readline

s = list(input().rstrip())[::-1]

def cal(start):
    r = 0
    while s:
        a = s.pop()
        if a == "(" or a == "[":
            r += cal(a)
        elif start == "(" and a == ")":
            return 2 * max(1,r)
        elif start == "[" and a == "]":
            return 3 * max(1,r)
    
    # 리스트가 비었는데 최종 return 하지 못했다는 것은 괄호에 문제가 있음을 의미
    print(0)
    sys.exit()

ans = 0    
while s:
    ans += cal(s.pop())
print(ans)

([]()) 를 다시 예시로 보자면, 

 

처음 '('를 뽑아 cal() 함수가 호출되는데, 그 다음 요소인 '['를 뽑아 s로 지정하고 인자로 받은 '('는 start로 지정한다

만약 s가 열린 괄호라면 cal() 함수를 다시 호출한다 따라서 start가 '['이고 s가 그 다음 요소인 ']' 이다 이때는 start와 s 가 []로 닫히는 괄호이므로 3을 곱하고 리턴한다 (r을 1로 초기화하는 대신에, max(1, r) 를 썼다)

리턴된 값은 r에 더해진다

그 다음 뽑은 '('와 처음에 호출했던 함수의 인자 '('를 비교한다 - s가 열린 괄호이기 때문에 위와 같은 과정을 거쳐 2를 리턴한다

그 다음 뽑은 ')' 가 처음에 호출했던 함수의 인자 '('와 호응하기 때문에 지금까지 구한 r에 2를 곱하고 리턴

 

재귀함수를 while 문 안에서 호출하는 이유는 ()[] 처럼 끊기는 경우를 고려한 것 같다

 

이 코드가 훨씬 이해가 잘 되고 마음에 든다 ... 

 

 

코드 출처: https://my-coding-notes.tistory.com/343