[알고리즘/Swift] 2504 괄호의 값
문제 정보
- 문제 출처: 백준 온라인 저지
- 문제 링크: 2504번 괄호의 값
- 제출 언어: Swift
- 알고리즘 분류:
- 구현
- 자료 구조
- 스택
문제
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)
}