문제 정보


문제

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

한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.
만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.
X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.
예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다.
우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.

  • ‘()’ 인 괄호열의 값은 2이다.
  • ‘[]’ 인 괄호열의 값은 3이다.
  • ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
  • ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
  • 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.
  • 예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

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

입력

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

출력

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

//입력
(()[[]])([])

//출력
28

풀이

자주 풀어보던 스택을 이용한 올바른 괄호 구분 문제였는데 이 문제는 다른 문제들에 괄호열의 값을 정의하여 계산해야 했으므로 조금 더 생각할 것이 많았다
케이스를 세분화하면서 풀이를 진행하였다

  • 괄호를 여는 경우에는 stack에 넣어주고 해당 괄호값을 temp에 곱한다
  • 괄호를 닫는 경우에는
    • stack에서 하나의 원소를 pop하여 닫는 괄호랑 짝궁인 경우 (“[” - “]”)는 result에 temp를 더해준다
    • 이후 temp를 해당 괄호값으로 나눈다
  • stack이 비어있거나 괄호를 닫는 경우에 pop한 원소값이 짝궁이 안될 경우 result는 0으로 처리한다

이러한 알고리즘을 생각하면서 가장 헷갈려던 부분은 괄호를 닫는 경우였다
언제 temp를 나눠주고 result에 더하는 가에 대해 정하는 것이 매우 헷갈렸다

((([])))() 로 예를 들어보자.
주어진 괄호열을 순회하며 해당 원소가 index = 4인 ]일 때 바로 이전 값이 짝궁 괄호 [ 일 경우
이미 temp에는 겹친 여러 쌍의 괄호값이 계산되었으므로 result값에 더해주면 된다
하지만 이 겹친 문자열 뒤에 작은 문자열 ()도 처리해주기 위해서는 temp를 다시 초기화해야 하므로
직전 원소 값이 짝궁 괄호가 아닌 닫는 괄호들을 만날 때마다 temp를 나눠주는 것이다

코드

import Foundation

var lst: [Character] = Array(readLine()!)
var stack: [Character] = []
var result: Int = 0
var temp: Int = 1

for i in 0...lst.count-1 {
    if lst[i] == "(" || lst[i] == "[" {
        stack.append(lst[i])
        if lst[i] == "(" {
            temp *= 2
        }else{
            temp *= 3
        }
    }
    else{
        if let target = stack.popLast() {
            if lst[i] == ")" {
                if target != "(" {
                    result = 0
                    break
                }else{
                    if lst[i-1] == "(" {
                        result += temp
                    }
                }
                temp /= 2
            }else{
                if target != "[" {
                    result = 0
                    break
                }
                else{
                    if lst[i-1] == "[" {
                        result += temp
                    }
                }
                temp /= 3
            }
        }else{
            result = 0
            break
        }
    }
}
if stack.isEmpty{
    print(result)
}
else{
    print(0)
}