[Kotlin, S2] 백준 2716번 원숭이 매달기

출처: unsplash.com

 

원숭이 매달기(2716번)

Silver 2

#자료 구조 #트리 #스택

 

문제 내용

 

 

문제 접근

입력은 오직 대괄호만 주어진다. 대괄호가 있으면 덩굴이 2개로 분리되는 것이다.

각 덩굴에는 동일한 수의 원숭이가 있어야 한다.

덩굴은 2개로만 나누어질 수 있다.

위 문제의 그림을 보면 각 덩굴 수에 맞는 원숭이들이 매달려 있다.

사진 1-1

 

첫 번째 덩굴의 원숭이 수는 각 덩굴에 4마리씩이다(2+ 2, 1 + 1 + 2).

오른쪽의 덩굴의 원숭이 수는 각 덩굴에 2마리씩이다(1 + 1, 2).

각 덩굴의 depth가 깊어질수록 필요한 원숭이의 수가 2배씩 늘어나게 된다.

 

덩굴은 무조건 2개씩으로만 나누어지기 때문에 한 덩굴의 depth가 깊어질수록 다른 덩굴도 깊어진 덩굴의 depth에 따라 늘어난 원숭이 수에 맞게 원숭이를 추가해 줘야 한다.

사진 1-1에서는 최대 깊이가 3이다. 그리고 필요한 원숭이의 수가 8마리이므로, 차수를 depth로 하는 2의 제곱수를 구해주면 된다.

 

이제 2의 depth승을 구해야 하는 사실은 알게 되었다.

그러면 어떻게 구할 수 있을까?

트리를 이용해서 구할 수 있지만 굳이 그렇게 구할 필요는 없을 것 같다. 트리를 다룰 줄 알면 지금 바로 트리를 구현해 문제를 해결하자.

트리를 모르는 우리는 대괄호의 방향에 따라 깊이를 측정할 수 있다.

대괄호 여는 부분(' [ ')이 들어오면 깊이를 증가시키고, 아닌 경우에는 깊이를 줄여 주면 된다.

사진 1-2

덩굴의 구조를 다음과 같이 깊이를 측정할 수 있다.

위 표를 보면 가장 깊을 때의 깊이가 3이다. 그러면 바로 2의 3승으로 정답을 구할 수 있다.

 

바로 코드로 나타내 보자.

 

<조건 1>

tree의 데이터가 여는 대괄호면 깊이를 증가시키고, 아니면 깊이를 감소시킨다.

그리고 현재 깊이와 측정된 최대 깊이 중 더 큰 값을 저장한다.

for (t in tree) {
    if (t == '[') current++
    else current--

    deep = max(deep, current)
}

deep이 측정된 최대 깊이이고, current가 현재 깊이이다.

current가 deep보다 크면 deep이 current로 갱신되는 방법으로 최댓값일 때의 경우를 구할  수 있다.

위 코드로 최심부의 깊이를 구할 수 있다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.max

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val case = readLine().toInt()

    for (i in 0 until case) {
        val tree = readLine()
        var deep = 0
        var current = 0

        for (t in tree) {
            if (t == '[') current++
            else current--

            deep = max(deep, current)
        }

        var res: Long = 1
        for (j in 0 until deep) res *= 2

        println(res)
    }
}

 

문제 풀이

덩굴의 구조를 입력받고 조건 1을 실행해 최심부의 깊이를 구해 준다.

정확한 깊이 측정을 위해 pow 함수를 쓰지 않고 for문을 사용해 주었다.

 

 

문제 해결 과정

pow 함수를 쓰면 25%에서 오답이 난다. 왜인지는 모른다. pow 함수를 쓰려면 double 타입으로 받아서 그런 문제가 생기는 것 같다.

알고리즘 분류는 자료 구조의 스택과 트리를 쓰라고 되어 있는데 수학적으로도 해결할 수 있다.