[백준/Python] 괄호의 값

이번 포스팅은 오답 풀이인 '✏️ 풀이 1'과 정답 풀이인 '✏️ 풀이 2', '✏️ 풀이 3'으로 3가지 코드가 정리되어있다.
가장 짧고 깔끔한 풀이는 '✏️ 풀이 3'로, 빠르게 정답 풀이를 보고 싶다면 '✏️ 풀이 3'를 참고하기 바란다.
반례 테스트케이스 리스트는 맨 아래쪽에 있으니 정답 코드를 제외한 해당 부분만 보고 싶다면 '🧐 반례 리스트'로 이동하길 바란다.

---

📄 문제

백준
난이도 : Silver 1
문제 제목 : 괄호의 값

✏️ 풀이 1 / 오답

import sys

str = sys.stdin.readline().strip()  # 입력 값
stack = []  # 괄호의 쌍을 확인하기 위한 스택
total = 0   # 총 괄호의 값 (정답)
current_calc = 0    # 부분 곱하기 연산 등을 위한 현재(일부) 계산 값
is_continuity = False   # 여는 괄호가 연속으로 등장했는지 확인하기 위한 플래그
error = False   # 에러 플래그

def close_func(input_str):
    global total, current_calc, is_continuity
    # input_str 값에 따른 페어 괄호
    pair = '(' if input_str == ')' else '['
    # 페어 값에 따른 피연산자
    operand = 2 if pair == '(' else 3
    # 여는 괄호의 연속이 깨졌으니 is_continuity는 False
    is_continuity = False

    # 닫힌 괄호가 등장했는데 스택이 비어있거나, 스택의 마지막 값이 페어와 다르면 에러 발생
    if len(stack) < 1 or stack[-1][0] != pair:
        sys.exit(0)
    # 곱하기 연산일 시
    elif stack[-1][1] == '*':
        # 이전에 현재 괄호 내부에서 괄호들를 pop한 이력이 있어 해당 괄호 값들을 먼저 더해줘야 할 시
        if stack[-1][2] == True:
            total += current_calc
            current_calc = 0
            total *= operand
        else:
            current_calc *= operand
    # 더하기 연산일 시
    else:
        current_calc += operand
    stack.pop()


for v in str:
    # 여는 괄호일 시
    if v == '(' or v == '[':
        # 여는 괄호 등장 시, 이전에 계산해왔던 current_calc가 존재하면 total에 더하고 0으로 리셋
        if current_calc != 0:
            total += current_calc
            current_calc = 0
            # (()[[]])의 경우, '()'가 pop된 후 첫번째 '('에 대한 stack 요소의 2번째 인덱스 위치 값을
            # True로 변경하여, 내부에 pop된 요소가 있다는 것을 알린다.
            # 이를 통해 이후 첫번째 '('에 대한 ')' 등장 시 '()'와 '[[]]'의 계산 값을 더한 후 *2를 할 수 있다.
            if len(stack) >= 1: stack[-1][2] = True
        
        # 스택 마지막 요소의 1번째 요소의 값이 None이라면, 해당 괄호의 연산이 곱하기인지 더하기인지 저장한다.
        if len(stack) >= 1 and stack[-1][1] == None:
            # 여는 괄호가 연속되었다면 이전 저장된 여는 괄호를 꺼낼때 곱하기 연산이다.
            if is_continuity:
                stack[-1][1] = '*'
        stack.append([v, None, False])  # ['(' 혹은 '[', 해당 문자열 pop될 때의 연산자, 내부 괄호가 삭제되었는지 여부]
        is_continuity = True
    # 닫힌 괄호일 시
    else:
        close_func(v)

if not stack:
    print(total + current_calc)
else:
    print(0)

✅ 풀이 한줄 설명:
스택에 여는 괄호를 [{1}, {2}, {3}]의 형태로 저장하여 닫힌 괄호가 나올때 가장 최근에 스택에 저장된 값의 상태에 따라 적절한 작업을 수행한다.
스택의 요소

• {1}: '(' 혹은 '['로, 괄호 문자열을 저장한다.
• {2}: 해당 요소가 pop()될 때(짝이 되는 닫힌 괄호를 만날때), 해주어야 할 연산자를 저장한다.
  이때 해당 요소를 스택에 저장할 때는 이 값을 알 수 없으니, 다음 요소를 스택에 저장할 때 여는 괄호의 연속성에 따라 '*' 혹은 '+'을 저장한다.
• {3}: 해당 괄호 내에 ()[[]]와 같이 괄호들이 서로 더해진 후 해당 괄호 값에 맞춰 곱해져야 할 때를 대비한 boolean 값이다. True일 경우, 해당 괄호 내에 덧셈할 괄호 값들이 있다는 뜻으로 덧셈 먼저 한 후 곱셈을 한다.
  ⚠️ (()[[]])의 경우 첫 번째 '('가 pop()되는 시기에 이미 내부 '()'가 제거되었기 때문에 첫 번째 '(' 요소에 대해 내부에 덧셈이 있다는 사실을 알려야 한다.

✅ 풀이 자세한 설명:
위의 코드에 주석을 자세히 달았으니 참고 바란다.
사실 오답이기 때문에 패스해도 상관없다.

🚫 오답 설명
해당 코드는 특정 테스트케이스에서 오답을 반환한다.
예를 들어, ([()(())](())([[]]()))()[()]의 경우를 보자.
([[]]())에서 '('를 스택에 넣을 때, 아래의 for문 내의 코드 때문에 [[]]의 결과가 total로 들어가면서 문제가 발생한다.

if current_calc != 0:
    total += current_calc
    current_calc = 0

이렇게 되면 이후 ([[]]())에서 '()'을 계산한 후 '[[]]'과 '()'을 먼저 더하고 *2를 하려할 때 total += current_calc을 먼저 하고 total *= 2를 한다. 그러면 이미 total에는 이전 괄호값들이 쌓여있기 때문에 원하는 값보다 큰 값이 나오게 된다.
❗️ 해결 방법
따라서 따로 [[]]의 값을 저장할 위치를 두어야 한다.
그러나 그렇게 하기에는 코드도 너무 길어지고 복잡해지기 때문에 굳이 여기서 무언가를 추가하기 보다 더 좋은 풀이를 다시 생각해보는 것이 좋을 것 같다.

✏️ 풀이 2

import sys

input_str = sys.stdin.readline().strip()

def go(string):
  if string == '':
    return []
    
  stack = []
  temp = []
  log = ''
  
  for v in string:
    if v == '(' or v == '[':
      stack.append(v)
    else:
      if v == ')':
        pair = '('
      else:
        pair = '['
      if not stack or stack.pop() != pair:
        print(0)
        sys.exit(0)

    log += v

    if stack == []:
      if log[0] == '(':
        num = 2
      else:
        num = 3

      if len(log) == 2:
        temp.append(num)
      else:
        temp.append([str(num) + '*', go(log[1:-1])])
      log = ''

  if stack:
    print(0)
    sys.exit(0)
  return temp


def cal(arr):
  if isinstance(arr, int):
    return arr

  if arr[0] == '2*':
    return 2 * cal(arr[1:])
  if arr[0] == '3*':
    return 3 * cal(arr[1:])

  return sum(map(lambda x: cal(x), arr))


arr = go(input_str)
print(cal(arr))

✅ 풀이 한줄 설명:
친구가 푼 풀이인데, 재귀함수(go, cal)와 스택을 사용하여 풀었다.

• go: 괄호 수식을 숫자로 이루어진 배열 형태로 바꿔준다. 예를 들어 (()[[]])([])는 [['2*', [2, ['3*', [3]]]], ['2*', [3]]]로 바꿔준다.
• cal: go의 결과 배열을 받아 결과 값을 계산해준다. 예를 들어 [['2*', [2, ['3*', [3]]]], ['2*', [3]]]가 들어오면 $(2 * (2 + (3 * 3))) + (2 * 3)$ 으로 변경하여 계산 결과 값인 28을 반환한다.

✅ 풀이 자세한 설명:
아래 설명을 읽고 위의 코드를 읽어보면 아마 이해가 쉽게 될 것이다.

• go
  괄호 수식을 숫자로 이루어진 배열 형태로 바꿔주는 재귀함수이다. stack에는 순서대로 괄호 값을 (여는 괄호는) 넣고 (닫힌 괄호가 나올 시) 빼주고, log에는 우선 순서대로 모든 괄호 값을 저장한다.
  만약 stack이 비게 되는 순간이 올 경우, log[0]을 확인하여 괄호에 맞는 적절한 값을 num에 저장한 후, log의 길이에 따라 적절히 변환된 수식 배열을 temp에 저장한다. 그리고 log는 비워준다.
• cal
go의 결과 배열을 받아 결과 값을 계산해주는 재귀함수이다. arr[0] == '2*'이면 나머지 arr[1:]을 다시 cal()로 실행한 값에 2를 곱하고, arr[0] == '3*'이면 3을 곱한다.

✏️ 풀이 3

import sys


bracket = sys.stdin.readline().strip()
length = len(bracket)
stack = []
num = 1
total = 0

for i in range(length):
    b = bracket[i]
    pair = '(' if b == ')' else '['
    operand = 2 if b == ')' else 3

    if b == '(':
        num *= 2
        stack.append(b)
    elif b == '[':
        num *= 3
        stack.append(b)
    else:
        if not stack or stack[-1] != pair:
            total = 0
            break
        if bracket[i-1] == pair:
            total += num
        num //= operand
        stack.pop()

if stack:
    total = 0
print(total)

✅ 풀이 한줄 설명:
다른 사람이 푼 풀이인데, 스택을 이용하여 푼 풀이이다. 알고리즘 강의 유튜버 바킹독 뿐만 아니라 많은 사람들이 이 방법으로 풀었다.
무작정 더하기가 나오면 더하고 곱하기가 나오면 곱하는 것이 아니라, 기본적인 곱셈공식인
$a * (b + c) = (a * b) + (a * c)$
를 이용한 풀이이다.
➕ 스택의 활용(괄호쌍) 문제라고 '닫힘 괄호'가 나올때 초점을 맞추지 말자. 열림 괄호가 나올 때 현재 항(작은 식)을 계산하고, 닫힘 괄호가 나올 때 이전 계산 값에 현재 계산했던 값을 더해주는 방식이다.

✅ 풀이 자세한 설명:
아래 설명을 읽고 위의 코드를 읽어보면 아마 이해가 쉽게 될 것이다. 중요한 부분 위주로 설명을 적어놓았다.

• num: 현재 계산 중인 식의 값이다.
• total: 총 괄호 식의 결과 값이다.
• for문
  b가 열린 괄호 중 '('이면 num *= 2를 하고 stack더 b를 넣어준다.
  b가 열린 괄호 중 '['이면 num *= 3를 하고 stack더 b를 넣어준다.
  b가 닫힌 괄호이면 우선 에러 핸들링을 하고, bracket[i-1] == pair인지 확인한다. 맞을 경우 total에 num을 더한 후 num //= operand를 해주고 stack.pop()을 한다.

정리하자면 다음과 같다.

1. $a * (b + c)$ 로 표현된 괄호 식을 $(a * b) + (a * c)$ 와 같이 변환하여 계산한다.
2. 이때 total에 값을 더하는 시기는 곱하기로 이루어진 작은 식의 가장 내부에 있는 괄호가 닫힐 때이다.
   ➕ 예를 들자면, (()[[]])([])의 경우
   첫 번째 ()이 닫힐때,
   [[]]의 안쪽 ]가 나타나 닫힐 때,
   ([])의 안쪽 ]가 나타나 닫힐때
   total에 그동안 곱해두었던 값이 더해지는 것이다.

🧐 반례 리스트

아래 반례 리스트는 직접 입력해본 값들과 백준 질문게시판에서 찾은 반례들이다. 특히 아래 10번부터 25번까지는 질문게시판에 hy2850님이 올려주신 '테스트 케이스 공유합니다' 게시글에서 참고했다.

1. 입력 값: ([()(())](())([[]]()))()[()]
   올바른 결과 값: 96
2. 입력 값: ()(
   올바른 결과 값: 0
3. 입력 값: (
   올바른 결과 값: 0
4. 입력 값: )
   올바른 결과 값: 0
5. 입력 값: ((()
   올바른 결과 값: 0
6. 입력 값: [[[[[[[[[[[[[[[]]]]]]]]]]]]]]]
   올바른 결과 값: 14348907
7. 입력 값: ([)]
   올바른 결과 값: 0
8. 입력 값: ]]
   올바른 결과 값: 0
9. 입력 값: ()([]
   올바른 결과 값: 0
10. 입력 값: ()[
    올바른 결과 값: 0
11. 입력 값: (()[])
    올바른 결과 값: 10
12. 입력 값: ((()[]))
    올바른 결과 값: 20
13. 입력 값: ((()[]))[]
    올바른 결과 값: 23
14. 입력 값: ((()[])[])
    올바른 결과 값: 26
15. 입력 값: ()[()]
    올바른 결과 값: 8
16. 입력 값: (()[[]])
    올바른 결과 값: 22
17. 입력 값: (()[[]])[]
    올바른 결과 값: 25
18. 입력 값: [()[()[()]]]
    올바른 결과 값: 78
19. 입력 값: ()[()]()[()]
    올바른 결과 값: 16
20. 입력 값: (()[()]()[()])
    올바른 결과 값: 32
21. 입력 값: (()[()]()[()])(()[()]()[()])
    올바른 결과 값: 64
22. 입력 값: [](()[()]()[()])(()[()]()[()])
    올바른 결과 값: 67
23. 입력 값: [](()[()]()[()])()(()[()]()[()])
    올바른 결과 값: 69
24. 입력 값: [](()[()]()[()])()(()[()]()[()])[]
    올바른 결과 값: 72
25. 입력 값: ((()[()]()[()])()(()[()]()[()])[])
    올바른 결과 값: 138

📦 GitHub

해당 문제, 풀이에 대한 GitHub Repository 링크는 다음과 같다.
GitHub - 백준(Silver) '2504. 괄호의 값'
GitHub - [8강] 스택의 활용 (수식의 괄호 쌍)/응용문제 '2504. 괄호의 값'

---

실버 문제이기도 하고 스택을 이용하면 될 것 같아 약간 쉽게 봤었는데 푸는데 진짜 오래 걸렸다...
처음에 규칙을 잘 찾고 정리를 한 후 코드를 작성해야 했는데 대충 느낌만 파악하고 코드를 작성했더니 반례 테스트케이스가 나올때마다 수정하느라 코드도 더러워지고 시간도 너무 오래 걸렸다. 결국 아예 새로 풀어야 했다.
꽤나 고생고생해서 푼 문제이고 친구까지 끌어들여 오랜 시간을 들여서 여러 방법을 생각해본 문제라 포스팅으로 남겨놓았다.
이 문제는 다음주 말쯤에 한 번 다시 풀어보아야 겠다.

➕ 참고로 '✏️ 풀이 2'의 경우 재귀라 시간이 초과되거나 너무 오래 걸리진 않을까 싶었지만, 입력 길이가 짧아서인지 40ms밖에 걸리지 않았다.