백준 2504번: 괄호의 값 (Python)

문제

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을 출력해야 한다. 

 

---

 

풀이

풀지 못했다. 와.. 스택 문제들은 다 리스트 써서 대충하면 되는 줄 알았는데, 감도 못 잡겠네.

 

최초로 제출한 잘못된 코드(볼 필요 없음)

string = input().rstrip()

def f(s: str) -> int:
    stack = []
    answer = 0
    count = 1
    for letter in s:
        if letter == "(":
            if count > 1:
                answer += count
            count = 1
            stack.append("(")
        
        if letter == "[":
            if count > 1:
                answer += count
            count = 1
            stack.append("[")

        if letter == ")":
            temp
            if stack == []:
                return 0
            elif stack[-1] != "(":
                return 0
            else:
                stack.pop()
                count *= 2
                
        if letter == "]":
            if stack == []:
                return 0
            elif stack[-1] != "[":
                return 0
            else:
                stack.pop()
                count *= 3
        print(answer)

    answer += count
    if stack == []:
        return answer
    return 0

print(f(string))

돌려보면, 예시 1에서 (2+9) * 2를 해야하는데, 2 + 9*2를 한다. 즉, 덧셈 연산이 안된다는 문제가 있었고, 해결 방법을 모르겠더라.

 

풀이

https://westernriver.tistory.com/7 선생님의 설명이 자세해서 보고 배우기 좋았다.

일단, 완벽한 형식인지 확인하는 함수를 정의한다. 주어진 괄호열이 올바른지 판단하는 과정이랑, 계산하는 과정을 동시에 하다보면 경우 나눌때 생각이 좀 꼬이더라.

이제부터 괄호열이 올바른 형식인지 판단하는건 맨 마지막에 if문으로 할 예정이니, 주어진 string은 무조건 (,[와 ],)이 잘 대응될 것이다. stack = []를 선언하고, input string에 대하여 for문을 돌면서,

1. 만약 "("이나 "["이 나오면 해당 문자를 스택에 넣는다.
2. 만약 ")"이나 "]"이 오면 2가지 경우가 있다.
   1. stack[-1]에 "("이나 "["이 없는 경우(올바른 괄호열 체크했기때문에 stack == []이나 매칭이 안 되는 경우는 없다.), stack에서 pop해주고 "("면 2, "["면 3을 넣어준다.
   2. stack[-1]에 숫자가 있는 경우, i = -1부터 숫자일 경우 스택에서 pop하고 더해주다가 괄호가 나오는 경우(무조건 나옴) 더한 값에 2 or 3을 곱해주고 스택에 다시 넣어준다.

풀고나니 스택 문제라기보단 아이디어가 중요해보인다. 스택에 숫자를 넣는다는 생각을 못했네...

 

 

코드

def is_correct(string):
    stack = []
    for s in string:
        if s == "(" or s == "[":
            stack.append(s)
        
        if s == "]":
            if stack and stack[-1] == "[":
                stack.pop()
            else:
                return False
        
        if s == ")":
            if stack and stack[-1] == "(":
                stack.pop()
            else:
                return False
    
    if stack == []:
        return True
    return False


def value(string):
    stack = []
    for s in string:
        if s == "(" or s == "[":
            stack.append(s)

        if s == ")":
            if stack[-1] == "(": # 처음 넣는 경우
                stack.pop()
                stack.append(2)
            else: # 숫자가 있는 경우: 매칭 안되는 경우는 없음.
                temp_sum = stack.pop()
                a = stack[-1]
                while(type(a) == int):
                    temp_sum += stack.pop()
                    a = stack[-1]
                stack.pop()
                temp_sum *= 2
                stack.append(temp_sum)

        if s == "]":
            if stack[-1] == "[":
                stack.pop()
                stack.append(3)
            else: # 숫자가 있는 경우: 매칭 안되는 경우는 없음.
                temp_sum = stack.pop()
                a = stack[-1]
                while(type(a) == int):
                    temp_sum += stack.pop()
                    a = stack[-1]
                stack.pop()
                temp_sum *= 3
                stack.append(temp_sum)
        #print(stack)
    return(sum(stack))


string = input().strip()
if is_correct(string):
    print(value(string))
else:
    print(0)

* 예제 입력 1을 넣었을 때 for문마다 stack을 출력해보면

['(']
['(', '(']
['(', 2]
['(', 2, '[']
['(', 2, '[', '[']
['(', 2, '[', 3]
['(', 2, 9]
[22]
[22, '(']
[22, '(', '[']
[22, '(', 3]
[22, 6]

과 같이 나온다. 이것도 보다보면 이해에 도움이 되더라.