BOJ 2504 괄호의 값

문제 : BOJ 2504 괄호의 값

두 종류의 괄호 (과), [과] 로 구성된 문자열의 괄호가
올바른 형태의 괄호인지,
올바른 형태라면 주어진 조건에 맞게 계산한 결과는 무엇인지를 구하는 문제이다.

1. 올바른 괄호인가?

여는 괄호 : (, [
닫는 괄호 : ), ]

문제의 조건에 따라서, 올바르지 않은 괄호 문자열은
'올바르지 않은 닫는 괄호' ( ) 또는 ] ) 를 가지는 괄호 문자열이다.
'올바르지 않은 닫는 괄호'란

1. 여는 괄호보다 먼저 오거나 ][]
2. 내부의 완성된 괄호를 제외한, 직전의 여는 괄호와 짝이 맞지 않거나 [()[()])
3. 괄호가 완전히 닫히지 않는 상태이다. (()([])

따라서, 입력된 괄호 문자열의 모든 닫는 괄호가
위 세가지 조건을 모두 만족하지 않는다면,
올바른 괄호 문자열이라고 할 수 있다.

구현

반복문을 통해 입력된 괄호 문자열의 괄호를 하나씩 순회하며 진행한다.

stack을 이용해서,

• 여는 괄호가 입력될 때는 조건없이 append() 하고
• 닫는 괄호가 입력될 때는 위의 조건을 이용해서 '올바른 닫는 괄호' 인지 확인한 뒤
  올바르지 않다면 반복문을 종료하고
  올바르다면 괄호가 완성된 것이기 때문에, 직전의 괄호를 pop() 해주었다.

괄호를 완성시키지 않고 pop() 을 통해 바깥으로 꺼내준 이유는
위 2번 조건의 '내부의 완성된 괄호를 제외한' 이라는 문장 때문인데,

완성된 괄호는 괄호가 올바른지 아닌지 판단하기 위해서 사용할 필요가 없을 뿐더러,
완성되지 않은 여는 괄호를 stack의 가장 위쪽(값을 넣고 꺼내는 위치)에 위치시키기 위함이다.

[ 코드 : 올바른 괄호 판단 ]

# boj 2504 괄호의 값

def check(target):
    stack = []                          # 괄호 문자를 입력대로 하나씩 push 또는 pop

    for p in target:
        # '여는 괄호'가 나타나면 append()
        if p == '[' or p == '(':
            stack.append(p)
        # '닫는 괄호'가 나타나면
        else:
            # 올바르지 않은 '닫는 괄호'일 경우 반복문 종료
            if len(stack) == 0 or {']':'[', ')':'('}[p] != stack[-1]:
                depth_sum[0] = 0
                break
            # 올바른 '닫는 괄호'일 경우 pop()
            else:
                stack.pop()

2. 괄호 연산

괄호가 둘러쌓인 개수를 괄호의 깊이라고 생각하고 접근했다.
만약 ([])이렇게 생긴 괄호 문자열이 있다면,
안쪽 괄호[]는 깊이가 1이고, 바깥쪽 괄호()는 깊이가 0인 식이다.

한 괄호 안에 들어있는 깊이가 같은 괄호끼리는 덧셈을,
안쪽 괄호의 값과 바깥쪽 괄호의 값끼리는 곱셈을 해주어야 한다.

가장 헷갈렸던것은 연산이 일어나는 시점인데,
괄호가 완성되며, 깊이가 감소하고, 곱셈을 해준 뒤, 연산이 누적되는 과정이
모두 올바른 닫는 괄호가 나타날 때(괄호 하나가 완성될 때) 일어나기 때문이다.

구현

깊이를 index로 하며 각 깊이의 계산 결과를 저장하는 배열로 문제를 해결했다.

여는 괄호가 나타날 때 마다 괄호의 깊이가 증가한다.

올바른 닫는 괄호가 나타날 때 마다 괄호의 깊이가 감소하며
이 때 현재 완성된 괄호의 깊이를 Index로 하여 결과값을 계산하는데,
이전 깊이(현재 깊이 + 1)의 누적된 계산값을 $\times$ 2 또는 $\times$ 3 해주어
다음 깊이(현재 깊이 - 1)에 저장해준다.

또한, 서로 다른 괄호 안에 있어도 깊이는 같을 수 있기 때문에
다음 깊이에 현재 깊이 계산값의 저장이 끝나면
현재 깊이의 계산값은 0으로 초기화 해준다.

문제에서 올바르지 않은 괄호일 경우 0을 출력하라는 조건을 주었기 때문에,
반복문 탈출 시에는
전체 괄호의 연산 결과를 가지는 0번 Index(깊이)의 배열값을
0으로 초기화 시켜준 뒤 종료한다.

[ 전체 코드 ]

# boj 2504 괄호의 값

import sys

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

def check(target):
    stack = []                          # 괄호 문자를 입력대로 하나씩 append 또는 pop
    depth = 0                           # 괄호의 깊이
    depth_sum = [0] * (len(target))   	# 괄호의 각 깊이에 대한 계산값을 저장, 갱신할 리스트

    for p in target:
        # '여는 괄호'가 시작되면 append(), 괄호 깊이 1 증가
        if p == '[' or p == '(':
            stack.append(p)
            depth += 1
        else:
            # 올바르지 않은 '닫는 괄호'일 경우 결과값에 0 저장 후 반복문 종료
            if len(stack) == 0 or {']':'[', ')':'('}[p] != stack[-1]:
                depth_sum[0] = 0
                break
            # 올바른 '닫는 괄호'일 경우 pop(), 계산
            else:
                stack.pop()
                
                # 곱 연산을 위해, 현재 계산된 값이 없다면 초기값 1로 저장
                depth_sum[depth] = 1 if depth_sum[depth] == 0 else depth_sum[depth]
                
                # 각 괄호에 대한 연산
                if p == ']':
                    depth_sum[depth] *= 3
                else:
                    depth_sum[depth] *= 2

                # 이전 깊이의 괄호에 대한 계산값을 더해줌
                depth_sum[depth-1] += depth_sum[depth]
                
                # 현재 값은 더해줬으므로 0으로 초기화
                depth_sum[depth] = 0
                
                # 괄호가 닫혔으므로 깊이 1 감소
                depth -= 1

    return depth_sum[0]

sys.stdout.write(f'{check(ps)}')

---

🤔생각해 볼 것

• 문제의 요구 사항을 분리해서 접근하자.