[Swift] BOJ 2504 괄호의 값 풀이 정리

[Swift] BOJ 2504 괄호의 값 풀이 정리

 

 

1. 문제 분석

 

1) 구해야할 값 분석

 

최종적으로 구해야 할 것은 괄호열의 값의 총합이다.

괄호가 성립된다고 해서 단순하게 값이 총합에 + 되는 것이 아니라, 어떤 괄호쌍에 쌓여 있게 되면, 2배 또는 3배로 곱해주어야 한다.

 

어떤 것이 중첩된 괄호인지 판단하고, 그에 맞게 괄호쌍의 점수를 판단해주는지가 문제이다.

 

볼드체 쳐진 부분을 어떻게 처리하는 지가 관건인 문제인 것이다.

 

 

2) 도구 선택

 

괄호는 쌍으로 이루어지기 때문에 스택 구조가 적합할 것이다. 괄호를 여는 부분을 스택에 넣고, 닫히는 괄호는 스택에서 제거해서 올바른 괄호쌍을 찾는다. 닫는 괄호가 나올 때, 열린 괄호와 짝이 맞는지를 확인해야 한다. 이때, 짝이 안맞으면 잘못된 입력이기 때문에 0을 출력해주면 된다.

 

3) 가중치 계산

 

(1) 괄호가 열릴 때

 

우선, 괄호가 열릴 때마다 temp에 가중치를 곱해주는 방식을 적용할 수 있다. 괄호의 종류에 따라 다른 가중치를 적용하며

 

• ()는 가중치 2

• []는 가중치 3

 

초기 temp 값은 1로 두고, 괄호가 열릴 때마다 해당 괄호의 가중치를 temp에 곱한다.

 

(2) 임시 변수의 변화 추적

 

만약 괄호가 열리는 구조가 ( ( [라면, 각각의 괄호가 열릴 때마다 temp에 곱셈이 적용된다.

 

• 처음 (가 열리면 temp *= 2 -> temp = 2

• 두 번째 (가 열리면 다시 temp *= 2 -> temp = 4

• 마지막으로 [가 열리면 temp *= 3 -> temp = 12

 

따라서 괄호가 닫히기 전, temp의 값은 12. 이 값은 중첩된 괄호 구조에 대한 가중치를 반영한 값.

 

(3) 괄호가 닫힐 때

 

괄호가 닫히면, 닫힌 괄호가 바로 이전에 열린 괄호와 맞닿아 있는지 확인한 후 result에 가중치를 반영해야 한다. 예를 들어, 괄호가 [ ]와 같이 바로 닫힌다면, temp의 현재 값을 result에 더해준다.

 

• temp 값이 현재 12일 때, [와 ]가 짝을 이루는 경우 12를 result에 더해준다.

 

(4) 계속해서 temp를 조정

 

닫힌 괄호마다 가중치가 반영된 값은 result에 합산된다. 그런 다음, 해당 괄호의 가중치를 제거하기 위해 temp에서 다시 나누기를 진행한다.

 

• []의 경우 temp /= 3

• ()의 경우 temp /= 2

 

이 과정을 반복하며 괄호가 닫힐 때마다 result는 최종 가중치를 반영하게 되는 것이다.

 

 

4) 올바른 값 더하기

 

(1) 짝이 맞을 때 값 더하기

 

괄호가 열릴 때마다 temp는 곱셈을 통해 중첩의 깊이에 따른 가중치를 추적하게 된다. 괄호가 닫힐 때는 바로 직전 괄호가 짝이 맞는지 확인해야 한다. 만약 짝이 맞는 괄호라면, 이전 값에 가중치가 적용된 temp 값을 result에 더한다.

 

예를 들어:

 

• () 괄호일 경우, temp 값에 2가 적용된다. 이때 괄호가 닫히면, 바로 이전에 열린 괄호가 (인 경우 해당 값 temp를 결과 값 result에 더해준다.

• [] 괄호일 경우, temp 값에 3이 적용되며 같은 방식으로 값을 더해준다.

 

(2) 값이 더해지는 시점

 

괄호가 닫히면서 temp에 적용된 가중치는 그 순간에 결과에 반영된다. 예를 들어, [ ( [ ] ) ]처럼 중첩된 구조에서는, 내부 [ ]가 닫힐 때 temp 값이 result에 더해진다. 그 다음 temp 값이 다시 조정되고, 더 바깥 괄호 ()가 닫히면 또 한 번 result에 값을 더하게 된다.

 

(3) 누적 더하기

 

괄호가 닫힐 때마다 해당 가중치 값이 더해지며, 이로 인해 중첩된 값들이 누적된다. 이렇게 각 괄호의 짝이 맞고 계산이 올바르게 적용될 때마다 result는 중첩 구조에 맞는 값을 얻게 된다.

 

(4) 가중치 해제

 

값이 더해진 후, temp는 해당 가중치를 해제하기 위해 다시 나눠야 한다. 예를 들어, ()가 닫히면 temp /= 2, []가 닫히면 temp /= 3을 적용해 가중치를 초기화한다. 이를 통해 다음 중첩에서 새로운 가중치를 정확하게 반영할 수 있다.

 

 

5) 예외 처리

 

괄호쌍이 맞지 않는 경우 -> 스택에 남아있거나 모든 괄호가 닫힌 경우 잘못된 입력이므로 즉시 0을 출력해주도록 하는 부분을 만들어 주면 될 것이다.

 

 

2. 코드 설명

 

func boj_2504() {
    let input = readLine()!.map { $0 }
    var result = 0
    var stack = [Character]()
    var temp = 1

    for (idx, paren) in input.enumerated() {
        if stack.isEmpty && (paren == ")" || paren == "]") {
            print(0)
            return
        }

        switch paren {
        case "(":
            temp *= 2
            stack.append(paren)
        case ")":
            if stack.last == "(" {
                if input[idx - 1] == "(" {
                    result += temp
                }
                stack.removeLast()
                temp /= 2
            } else {
                print(0)
                return
            }
        case "[":
            temp *= 3
            stack.append(paren)
        default:
            if stack.last == "[" {
                if input[idx - 1] == "[" {
                    result += temp
                }
                stack.removeLast()
                temp /= 3
            } else {
                print(0)
                return
            }
        }
    }
    if !stack.isEmpty {
        print(0)
        return
    }

    print(result)
}

 

위에서 발상한 대로 구현한 것이다. 가중치와 더하기 부분을 철저하게 나누고, 곱할 때와 나눌 때를 구분해 주어야 한다.

괄호가 서로 등지고 있는 부분 )( 또는 ][ 일 경우, 현재 가중치에 값을 더해 result에 포함시킨다.

 

전체 괄호를 다 나와서 계산을 해주는 것이 아니라, 괄호가 끝날 때 즉시 가중치를 곱한 채로 result에 더해 주는 것이다.

위의 예시 1번에 result가 들어가는 값을 차례대로 보자면

 

첫 번째에 result에 더해지는 값 : 4

두 번째에 result에 더해지는 값 : 18

세 번째에 result에 더해지는 값 : 6

 

2 * 2 + 3* 3* 2  + 3 * 3

 

닫는 부분에서 만약 이전 인덱스의 input 원소가 여는 괄호가 아닌 닫는 괄호인 경우, 이전에 계산한 부분이기 때문에, 가중치를 내려주고 스택에서 빼는 식으로 설계를 하면 된다. 그렇게 되면 가중치를 공유하지 않는 부분은 +로 연결되어 result에서 한 번에 계산을 끝낼 수가 있다.

 

중간 중간에 유효하지 않은 괄호쌍이 나올 경우 0을 출력하고, 마지막에도 input 순회가 끝났는데도 stack에 무엇인가 남아있다면, 올바르지 않은 괄호쌍이기에 0을 출력하도록 하면 된다.

 

temp로 가중치를 조정하는 부분이 발상하기 어려운 부분이었던 것 같다.