[백준 2504번] 괄호의 값

7632 단어 스택백준백준

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


1. 코드

import sys

exp = list(sys.stdin.readline().rstrip())
d = {
    ')': '(',
    ']': '['
}
ignore_flag = False
ans = 0
stack = []
for char in exp:
    if char not in d:
        stack.append(char)
        ignore_flag = False
    elif stack and d[char] == stack[-1]:
        stack.pop()
        if ignore_flag:
            continue
        # () 또는 [] 으로만 구성된 괄호라면 바로 답에 더해준다
        if not stack:
            if char == ')':
                ans += 2
            elif char == ']':
                ans += 3
        else:
            add_val = 2 if char == ')' else 3
            if stack.count('(') != 0:
                # 정상출력: [()[()[()]]] = 78
                # 수정: 카운팅된 횟수를 제곱으로 곱해야 한다.
                add_val *= pow(2, stack.count('('))
            if stack.count('[') != 0:
                add_val *= pow(3, stack.count('['))
            ans += add_val
            ignore_flag = True
    else:
        print('0')
        exit(0)

# 정상출력: ()([] = 0
# if문 추가 -> stack = ['('] 인 상태로 종료되면 실패 출력
if len(stack) == 0:
    print(ans)
else:
    print('0')

2. 코드 설명 및 후기

짝이 맞는 괄호가 제거되는 동작과정은 [스택] Valid Parentheses 문제를 통해 확인하자.

  • ignore_flag:True 상태일 경우 괄호가 짝이 맞는 쌍을 만나서 pop() 연산이 발생해도, 답이 증가하지 않는다.
입력값= (()[[]])([])
char=')' stack=['('], ans=4
char=']' stack=['(', '['], ans=22
char=']' stack=['('], ans=28

첫 번째로 괄호를 닫는 코드에서만 ans의 증가가 일어나고, 
새로운 `[` 또는 `(`가 오기 전까지 닫는 괄호의 ans의 증가 연산은 수행하지 않는다. 

이 문제가 생각보다 어려웠다. char에 노란색 입력값들이 들어올 때, ans 값이 증가하지 않게 구현해야 하는 부분에서 많은 시간을 소요했다. 결국에는 True, False 로 노란색 상태임을 체크하는 플래그를 도입하여 문제를 해결할 수 있었다.

테스트 케이스 들은 여기서 확인할 수 있다.

좋은 웹페이지 즐겨찾기