[python] 백준 2504번 : 괄호의 값 (stack)

https://www.acmicpc.net/problem/2504

2504번: 괄호의 값

 

1. 성공한 코드 

def solution(s):
    n = len(s)
    result = 1
    answer = 0
    # stack 생성 
    stack = []
    for i in range(n):
        if s[i] == '(':
            stack.append('(')
            result *= 2
        elif s[i] == ')':
            # s[i-1] -> stack[-1]로 구현 
            # 위치를 바꾸어 구현하면 indexError 발생 ☆
            # if (stack[-1] == '[' and stack) or not stack:
            if not stack or stack[-1] == '[':
                return 0
            elif s[i-1] == '(':
                answer += result
            result //= 2
            stack.pop()
        elif s[i] == '[':
            result *= 3
            stack.append('[')
        else:
            if not stack or stack[-1] == '(':
                return 0
            elif s[i-1] == '[':
                answer += result
            result //= 3
            stack.pop()
    if stack:
        return 0
    return answer

data = input()
print(solution(data))

 

2. 에러 발생한 코드 

import sys
sys.stdin = open('br.txt', 'r')

# 반례 : [[()]]()]]
# why? stack을 사용하지 않으면
# 짝이 없는 마지막-1, 마지막 번째의 ']' 에 대한 문제 인식 불가능
def solution(s):
    n = len(s)
    result = 1
    answer = 0
    for i in range(n):
        if s[i] == '(':
            result *= 2
        elif s[i] == ')':
            if s[i-1] == '[':
                return 0
            elif s[i-1] == '(':
                answer += result
            result //= 2
        elif s[i] == '[':
            result *= 3
        else:
            if s[i-1] == '(':
                return 0
            elif s[i-1] == '[':
                answer += result
            result //= 3

    return answer

data = list(input())
print(solution(data))

틀린 이유)

테스트 케이스에 대해서는 모두 통과하였지만 해당 코드에서 생각하지 못했던 반례는  '[[()]]()]]'였다.

이 문자열이 input으로 들어오면 마지막-1, 마지막 위치에 존재하는 ']'에 대해서 문제를 인식하지 못한다. 올바르지 못한 괄호열 중에서 '[ )', '( ]'에 대한 처리는 실수없이 진행하였지만

짝이 맞지 않는 경우도 올바르지 못한 괄호열에 속한다는 걸 인지하지 못했다.

이게 이 문제에서 stack을 이용하여 괄호의 짝맞춤 체크를 해야하는 이유이기도 하다.

그래서 stack을 사용하여 다시 구현해주었더니 정답 처리될 수 있었다.  마찬가지로 '((((([]' 와 같은 문자열이 반례로 들어올 수도 있다. 만약 짝이 맞는 경우에는 for문을 전부 돌고나면 stack은 비어있게 된다. 하지만 방금 말한 문자열이 들어간다면 stack에는 짝이 맞지 않는 문자 '(', '(', '(', '('가 남아있기 때문에 [] 만 인식해서 2를 return 하는 게 아니라 틀렸다는 의미로 0을 반환해야 한다. 

마지막 반례로는 '(()]'가 있다. 가운데 소괄호에 대해서는 문제가 없지만 맨처음 위치의 '('와 ']'가 만나면 0을 리턴해야 한다. 위 문제에서는 s[i-1] 번째 위치 즉 지금 비교하는 문자의 바로 왼쪽 문자와 짝맞춤 검사를 하였는데 이 부분이 잘못된 부분이다. 짝이 맞지 않아서 아직 stack에 대기 중인 '('나 '['와 짝이 맞는지를 체크하는 방식이 바람직하다.