[알고리즘/자료구조] 2504번 : 괄호의 값 - python

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

2504번: 괄호의 값

 

---

• 문제
• 소요시간: 22분, 실패

---

• 설계하기(접근방법) 

1. 문자열을 입력받는다, 스택을 선언한다

 

2. 알고리즘 해석

1) 만약 괄호가 열리면, stack에 append하고 괄호 내의 숫자는 후에 2or 3만큼 곱해진다

따라서 tmp 를 선언하여 그 변수를 제어해준다.

2) 괄호가 닫히고, 그 직전 괄호가 그 괄호의 쌍'()' or '[]' 이였다면 지금까지 곱해진 tmp만큼 ans에 더해줌그리고 stackpop()

또한 괄호가 닫히면 지금까지 곱해진 숫자를 ']' ,')'를 tmp에서 나누어준다.

3) 만약 괄호가 닫힐 때, 스택 가장 위에 있는 원소가 쌍이 안맞으면, 잘못된 괄호식이니 ans = 0 으로 해주고 break 해준다

 

예제를 해석하면 

( ( ) [ [ ] ] ) ( [ ] )

( -> stack에 append, tmp * 2 현재 tmp = 2

( -> stack에 append, tmp * 2 현재 tmp = 4

) -> 직전의 stack[-1] 이 ')'이니 ans += tmp, tmp //= 2 -> 현재 tmp = 2, ans = 4

[ -> stack에 append, tmp * 3 현재 tmp = 6

[ -> stack에 append, tmp * 3 현재 tmp = 18

] -> 직전의 stack[-1] 이 ']'이니 ans += tmp, tmp //= 3 -> 현재 tmp = 6, ans = 22

] -> 직전의 stack[-1]  ']'가 아님 tmp //= 3 만 진행 현재 tmp = 2,

) -> 직전의 stack[-1]  ')'가 아님 tmp //= 2 만 진행 현재 tmp = 1,

( -> stack에 append, tmp * 2 현재 tmp = 2

[ -> stack에 append, tmp * 3 현재 tmp = 6

] -> 직전의 stack[-1] 이 ']'이니 ans += tmp, tmp //= 3 -> 현재 tmp = 2, ans = 28

] -> 직전의 stack[-1]  ']'가 아님 tmp //= 3 만 진행 현재 tmp = 1,

 

ans = 28

---

 

• 코드(출력)

stack = []

n = list(input())
ans = 0
tmp = 1

for i in range(len(n)):  # (()[[]])([])
    if n[i] == '(':
        stack.append(n[i])
        tmp *= 2
    elif n[i] == '[':
        stack.append(n[i])
        tmp *= 3
    elif n[i] == ')':
        if not stack or stack[-1] == '[':
            ans = 0
            break
        if n[i-1] == '(':
            ans += tmp
        tmp //= 2
        stack.pop()
    elif n[i] == ']':
        if not stack or stack[-1] == '(':
            ans = 0
            break
        if n[i-1] == '[':
            ans += tmp
        tmp //= 3
        stack.pop()

if stack:
    print(0)
else:
    print(ans)

---

• 얻어갈 부분

1. 스택 자료구조를 사용할 때, 스택 하나로만 제어하려고 하지 말고, 필요하다면 추가적인 리스트나 변수를 선언하여 흐름을 제어해야 할 것이다.