[BOJ] 파이썬 백준 2504번 괄호의 값

문제. 백준 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 이하이다.

출력

첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다. 

 

 

출처 : 백준 2504번 괄호의 값

2504번: 괄호의 값

---

나의 풀이 in Python

# 괄호 입력
brackets = input().strip()

# 괄호가 제대로 되어 있는지 여부 체크
def check_brackets(bs):
    stack = []
    for b in bs:
        if b == '(' or b =='[':
            stack.append(b)
        elif b == ')' and stack:
            # 괄호 적중 제거
            if stack[-1] == '(':
                stack.pop()
            else:
                stack.append(b)
        elif b ==']' and stack:
        	# 괄호 적중 제거
            if stack[-1] == '[':
                stack.pop()
            else:
                stack.append(b)
        else:
            stack.append(b)
    # for문이 끝나고 stack에 값이 있다면, 괄호가 정확히 맞지 않은 문자열.
    if stack:
        return False
    else:
        return True

# 올바른 괄호일 때의 괄호 수식
def solution(bs):
    stack = []
    for b in bs:
        if b == '(' or b == '[':
            stack.append(b)
        elif b ==')': # and stack: x
            # 괄호 적중 () : 2
            if stack[-1] == '(':
                stack[-1] = 2
            # 겹겹이 쌓여있을 경우
            else:
                temp = 0
                # 스택은 LIFO이므로 뒤에서부터 수식
                for i in range(len(stack)-1,-1,-1):
                    # temp의 값 수식
                    if stack[i] =='(':
                        stack[-1] = temp * 2
                        break
                    # 스택에 숫자가 있을 경우 제거해주면서 temp에 저장
                    else:
                        temp += stack[i]
                        # print(temp)
                        stack.pop()
        elif b == ']':
            if stack[-1] == '[':
                stack[-1] = 3
            else:
                temp = 0
                for i in range(len(stack)-1,-1,-1):
                    if stack[i] =='[':
                        stack[-1] = temp * 3
                        break
                    else:
                        temp += stack[i]
                        # print(temp)
                        stack.pop()
    return sum(stack)

# 최종 괄호 수식
if check_brackets(brackets) == False:
    print(0)
else: print(solution(brackets))

조금의 난이도가 있는 괄호 문제입니다. 괄호 문제를 풀 때는 스택을 사용하지 않으면 못푼다고 할 정도로 스택이 중요하게 사용됩니다. 많은 코테에서도 자주 나오기 때문에 다양한 괄호 문제를 풀어보고 코드를 체득하는 것이 중요한 것 같습니다.

 

사실, 저도 많이 헷갈리고 어렵다고 느껴서 잘하시는 분들의 코드를 참고하며 풀었습니다.

설명은 주석을 통해 달아놨고 중요한 점은 LIFO(Last In First Out)인 스택의 특성을 잘 활용해야 한다는 점입니다.