[Python] 2504 - 괄호의 값 (실버1)

1. 문제 설명

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

2504번: 괄호의 값

 

---

2. 아이디어

굉장히 유명한 문제 중 하나로 전형적인 stack 자료구조를 이용한 풀이방법을 썼다.

입력받은 값이 '[', '(', ')', '(', '(', ')', '[', ']', ')', ']'라고 하자.

우선 스택에 '['라는 정보를 담아놓고 그 다음에 들어오는 정보를 확인한다.

'('는 '['와 매칭되는 쌍이 아니므로 마찬가지로 스택에 쌓는다.

다음 정보는 ')'이므로 바로 직전의 '('와 쌍이 될 수 있으므로 pop()하여 스택에서 빼낸다.

그럼 현재 스택에 쌓인 정보는 다시 '['가 된다.

stack	input
'['	'['
'[', '('	'('
'['	')'
'[', '('	'('
'[', '(', '('	'('
'[', '('	')'
'[', '(', '['	'['
'[', '('	']'
'['	')'
None	']'

즉, 최종적으로 스택에 아무런 정보도 담겨있지 않아야 적합한 괄호 문자열이라고 볼 수 있다.

 

만약 여기서 효율을 더 올리고 싶다면 ')'나 ']'가 들어왔을 때 바로 사라지지 않는 문자열의 경우
절대 괄호열이 성립될 수 없다. (')'와 ']'를 없앨 수 있는 방법이 존재하지 않음.)
즉, 이 경우를 예외처리하면 조금 더 빨라진다. 난 귀찮아서 구현 안 했었다.

 

여기까지하면 끝인 줄 알았는데 나는 정작 뒤에가 더 어려웠다.

괄호를 pop하면서 연산을 해야하는데 아무생각없이 하면 연산 순서가 꼬여버린다.

사실 곱하기 연산 순서를 생각해보면 간단하게 해결되는 문제였다.

 

위의 표를 다시 한 번 보자.

만약 저대로 입력이 된다면 output은 3 x (2 + 2 x (2 + 3)) = 36 이 되어야 한다.

스택을 이용해서 문제를 풀이했기 때문에 괄호가 묶여있음을 컴퓨터가 인지하고 있어야 한다.

하지만 이렇게 놓고 계산을 이어나가면 순서 맞추기가 굉장히 힘들어진다.

그런데 곱셉 규칙을 생각해서 괄호를 그냥 풀어버리면 사실 간단한 문제가 된다.

(3 x 2) + (3 x 2 x 2) + (3 x 2 x 3) = 36

 

즉, 괄호가 열리면 해당하는 값만큼 곱셈을 하여 저장하고 flag를 1로 저장한다.

여기서 flag는 왜 필요한가?

'(', '[', ']', ')' 라는 괄호열이 들어왔을 때, '('와 '['가 들어온 시점에서

value에는 이미 2*3이라는 값이 저장되어 있다가 ']'가 들어오면 total값에 더하는 로직이다.

그런데 flag가 없으면 ')'가 닫히면서 또 한 번 연산과정을 거치기 때문에 값이 2배가 된다.

 

스택 자료구조를 쓰는 것보다 이 부분이 훨씬 생각해내기 어려웠었던 것 같다.

 

---

3. 코드

def check_bracket(bracket, stack):
    flag, value, total = 0, 1, 0

    for i in bracket:
        if stack[-1] == '(' and i == ')':
            if flag == 1:
                total += value
                flag = 0
            value //= 2
            stack.pop()
        elif stack[-1] == '[' and i == ']':
            if flag == 1:
                total += value
                flag = 0
            value //= 3
            stack.pop()
        else:
            stack.append(i)
            if i == '(':
                value *= 2
                flag = 1
            elif i == '[':
                value *= 3
                flag = 1

    if len(stack) != 1: # 최종적으로 stack에 '0'만 존재해야 한다.
        return 0
    else:
        return total

def solution():
    bracket = input()
    stack = ['0']
    result = check_bracket(bracket, stack)
    print(result)

solution()