[백준] 2504 괄호의 값

문제

www.acmicpc.net/problem/2504

 

 

코드

string = input()
stack = []
answer = 0

for s in string:
    if s == "(" or s == "[":
        stack.append(s)
    elif s == ")":
        sum = 0
        while stack:
            top = stack.pop()
            if top == "[" or top == "]": # 올바르지 못한 괄호
                print(0)
                exit(0)
            elif top == "(":
                if sum == 0: # () 일 경우
                    stack.append(2)
                else: # (X) 일 경우
                    stack.append(2 * sum)
                break # ( 괄호 만났으면 다음 괄호문자열 받기
            else: # ( 만날 때까지 숫자 더하기
                sum += top
    elif s == "]":
        sum = 0
        while stack:
            top = stack.pop()
            if top == "(" or top == ")": # 올바르지 못한 괄호
                print(0)
                exit(0)
            elif top == "[":
                if sum == 0: # [] 일 경우
                    stack.append(3)
                else: # [X] 일 경우
                    stack.append(3 * sum)
                break  # [ 괄호 만났으면 다음 괄호문자열 받기
            else: # [ 만날 때까지 숫자 더하기
                sum += top

for num in stack:
    if type(num) != int:
        print(0)
        exit(0)
    else:
        answer += num

print(answer)

 

풀이

- 아이디어

 

예시 괄호: ( [ ] )

1. 우선, 괄호가 바로 짝이 맞는 경우부터 생각하기
   1. stack에 "[" 가 들어있고, string이 "]" 라면 바로 괄호 짝이 맞는다.
   2. 괄호 짝을 맞추면 괄호에 해당하는 숫자(1번의 경우 '3')로 변환해 다시 스택에 넣는다.
2. (X) 경우로 확장시키기
   1. 이 경우 1번 과정을 거쳤다면 실제 stack에는 "(3" 가 들어있게 된다.
   2. string이 ")" 라면 stack.pop() 을 진행하면서 "(" 가 나올 때까지 숫자를 더한다.

- 방법

1. "(", "[" 가 들어오면 stack에 넣는다.
2. ")" 괄호가 들어오면 "(" 괄호를 만날 때까지 stack.pop() 을 하며 sum 변수에 더한다.
3. "(" 괄호를 만났다면 stack에 숫자로 변환해 다시 스택에 넣는다.
   1. sum 변수가 0 이라면 "()" 와 같이 빈 괄호인 경우이므로 2만 넣는다.
   2. sum 변수가 0이 아니라면 "(sum값)" 이므로 2 * sum 계산을 해서 넣는다.