[kotlin] 백준 6198번 - 옥상 정원 꾸미기

코틀린 풀이입니다.

해당 문제는 for문으로 순회할 경우 시간초과가 발생하며, 발상의 전환과 함께 stack으로 풀이하여야 풀리는 문제입니다.

스택문제인 것이란 힌트를 알고도, 발상의 전환을 하지 못하여 오래 헤매어 정리해 놓습니다.

스택으로 풀이되는 (전형적인) 문제 유형인듯 합니다.

https://www.acmicpc.net/problem/6198

6198번: 옥상 정원 꾸미기

---

문제 설명

도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어 한다.

i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다. i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2,.... , N이다.
그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그다음에 있는 모든 빌딩의 옥상은 보지 못한다.
예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우

• 1번 관리인은 2, 3, 4번 빌딩의 옥상을 확인할 수 있다.
• 2번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 3번 관리인은 4번 빌딩의 옥상을 확인할 수 있다.
• 4번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 5번 관리인은 6번 빌딩의 옥상을 확인할 수 있다.
• 6번 관리인은 마지막이므로 다른 빌딩의 옥상을 확인할 수 없다.

따라서, 관리인들이 옥상정원을 확인할 수 있는 총 수는 3 + 0 + 1 + 0 + 1 + 0 = 5이다.

---

예시 입출력

입력

6
10
3
7
4
12
2

출력

5

---

풀이

문제 그대로, 높은 빌딩에서 어떤 빌딩을 벤치마킹할 수 있는가? 가 아니라, 현재 빌딩을 볼 수 있는 빌딩은 몇 개인가?로 접근해야 비교적 간단히 이해할 수 있습니다.

스택에는 현재 인덱스가 되는 빌딩을 기준으로 볼 수 있는 빌딩들이 포함되어 있습니다. 볼 수 없다면 pop을 하여 삭제합니다.

이렇게 접근하였을 때 이미 더 높은 빌딩을 만나 현재 시점에서 볼 수 없는 빌딩은 삭제되어 더 이상 순회하지 않으므로, 이중 for문보다 더 효과적으로 탐색할 수 있습니다.

typealias Stack<T> = MutableList<T>

private fun <T> Stack<T>.push(item: T) = add(item)
private fun <T> Stack<T>.pop(): T? = removeLastOrNull()
private fun <T> Stack<T>.peek(): T? = lastOrNull()

class BOJ6198 {
    fun solution(): Long {
        val br = System.`in`.bufferedReader()
        val num = br.readLine().toInt()
        val buildings = arrayOfNulls<Long>(num).map { br.readLine().toInt() }

        val stack: Stack<Int> = mutableListOf()
        var answer = 0L

        for(building in buildings) {
            while (stack.isNotEmpty() && stack.peek()!! <= building) {
                stack.pop()
            }
            stack.push(building)
            answer += stack.size - 1
        }

        return answer
    }
}