[백준/python] 2504 괄호의 값

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

2504번: 괄호의 값

 

• 사용언어 : python
• 알고리즘 : 구현, 스택, 자료 구조
• Solved.ac Tier : Silver I

 

python 코드

1. 문제 정리

어렵지 않은 문제라고 생각하고 접근 했으나, 꽤나 해결 하는데 오래 걸린 문제이다.

사람 머리로 하면 쉬운데... 구현 하려니 머리가 너무 복잡해졌다. 어느 부분에서 곱셈을 하고, 덧셈을 해야 할지 생각 해야 하는 문제였는데, 아이패드로 몇 번 그려보다가 도저히 안되서 직접 코드로 구현 해보다가 해결 한 문제이다. 

일반 괄호 문제처럼, 괄호의 짝이 맞는지 스택으로 먼저 확인하고, 아니라면 잘못된 괄호 입력이기 때문에 0을 출력해주면 된다. 
초기 값을 1로 두고 '(' 괄호가 열릴 때 2를 곱하고, '[' 괄호가 열릴 땐 3을 곱하고, 닫을 땐 다시 나누기 2, 3을 해주는 방식이다.

그럼 결과가 무조건 1일텐데 어떻게 계산을 하느냐? () [] 처럼 [ 인덱스 바로 뒤 인덱스를 확인하여 ] 괄호가 오는, 즉 여는 괄호 바로 뒤가 닫친 괄호인 경우에만 결과 값에다가 덧셈을 한다. 

이런 방식이면 주어진 문제에서 답을 도출 해 낼 수 있다.

2. 완성 코드

import sys

input = sys.stdin.readline().rstrip()

list = []
isAns = True
val = 1
ans = 0

for i, str in enumerate(input):
    if str == "(":
        list.append(str)
        val *= 2

    elif str == "[":
        list.append(str)
        val *= 3

    elif str == ")":
        if not list or list[len(list) - 1] == "[":
            isAns = False
            break
        if input[i-1] == "(":
            ans += val
        list.pop()
        val //= 2

    elif str == "]":
        if not list or list[len(list) - 1] == "(":
            isAns = False
            break
        if input[i-1] == "[":
            ans += val
        list.pop()
        val //= 3

if not isAns or list:
    print(0)
else:
    print(ans)