[스택] 백준 2504: 괄호의 값

문제: 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.

1. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.
2. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.
3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.

예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.

1. ‘()’ 인 괄호열의 값은 2이다.
2. ‘[]’ 인 괄호열의 값은 3이다.
3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다.

---

입력: 첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.

---

 

실버 1짜리 문제지만, 정형화된 알고리즘을 적용하기만 하면 되는 일부의 골드 4나 5 정도 되는 문제들보다 어려운 느낌이다.

로직이 생각나지 않는다면 틀릴 수밖에 없다. 이런 유형을 연습하기 위해선 평소 머리 쓰는 문제를 많이 풀어보는 수 밖엔 없는 것 같다.

 

먼저 로직을 생각해 보자.

나는 이 문제를 크게 2가지로 나누어 생각했다.

1. 괄호가 제대로 열리고 닫히는지 판단

2. 제대로 닫힐 경우 괄호에 따른 점수 계산

 

2가지로 나누어 생각한 이유는 괄호가 제대로 닫혔는지 판단하는 로직과 괄호에 따른 점수 계산 로직이 조금 다른 조건을 기준으로 작성되어야 한다고 생각했기 때문이다.

 

먼저 괄호가 제대로 닫히는지 아닌지 판단하는 코드이다.

arr = list(input())
stack = []

for i in range(len(arr)):
    if stack == []: # 저장되어 있는 괄호가 없으면
        stack.append(arr[i])

    elif stack[-1] == '(':
        if arr[i] == ')':
            stack.pop(-1)
        else:
            stack.append(arr[i])

    elif stack[-1] == ')':
        stack.append(arr[i])

    elif stack[-1] == '[':
        if arr[i] == ']':
            stack.pop(-1)
        else:
            stack.append(arr[i])

    elif stack[-1] == ']':
        stack.append(arr[i])

if stack == []:
    print('올바른 괄호입니다.')
else:
    print('올바르지 않은 괄호입니다.')

스택에 괄호를 하나씩 담아 주고, 닫을 수 있는 괄호라면 지워준다. 괄호가 담긴 리스트를 모두 순회했을 때 stack이 비어있다면, 해당 괄호 문자열은 제대로 닫히는 괄호가 된다.

 

다음은 괄호에 따라 점수를 계산하는 코드를 추가한 버전이다.

로직이 바로 생각나지는 않았다. 한두시간정도 찬찬히 수정해가며 로직을 완성했다.

def well_gwal(arr):
    for i in range(len(arr)):
        if stack == []: # 저장되어 있는 괄호가 없으면
            stack.append(arr[i])

        elif stack[-1] == '(':
            if arr[i] == ')':
                stack.pop(-1)
            else:
                stack.append(arr[i])

        elif stack[-1] == ')':
            stack.append(arr[i])

        elif stack[-1] == '[':
            if arr[i] == ']':
                stack.pop(-1)
            else:
                stack.append(arr[i])

        elif stack[-1] == ']':
            stack.append(arr[i])

    if stack == []:
        return True
    else:
        return False

arr = list(input())
stack = []
index_score = {
    '(': 2,
    '[': 3
}
ans = 0
multi_ans = 0 # 조회중인 괄호의 값과 곱해줄 값을 의미
ans_list = []

if well_gwal(arr): # 괄호가 잘 닫힌다면
    for i in range(len(arr)):
        if stack == []:
            multi_ans = index_score[arr[i]] # 2
            ans = multi_ans
            stack.append(arr[i])
        else:
            if arr[i] == '(' or arr[i] == '[': # 스택이 비지 않은 상황에서, 여는 괄호가 들어오면
                multi_ans *= index_score[arr[i]]
                ans = multi_ans
                stack.append(arr[i])
            else:
                ans_list.append(ans)
                ans = 0
                if arr[i] == ')':
                    multi_ans //= index_score[stack[-1]]
                else:
                    multi_ans //= index_score[stack[-1]]
                stack.pop(-1)
    print(sum(ans_list))

else:
    print(0)

이 문제는 사람마다 풀이 방법이 많이 다를 것 같다.

알고리즘을 적용하는 문제라기 보다는 문제 해결력과 사고력을 요하는 문제라고 생각한다. 위에서도 언급했지만, 정해진 알고리즘만 적용하면 되는 대다수의 골드 4, 5 문제보다는 확실히 어려운 느낌이었다.