백준 6198번: 옥상 정원 꾸미기

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

문제 풀이

스택

stack = 현재 빌딩의 옥상을 확인할 수 있는 빌딩

answer = 옥상을 확인할 수 있는 빌딩 수의 합

1. 스택의 맨 위에서부터 확인하면서 현재 빌딩의 높이보다 큰 빌딩을 찾을때까지 스택에서 빌딩을 뺀다.

2. 이 과정에서 스택에 남은 빌딩들은 현재 빌딩의 옥상을 볼 수 있는 빌딩들이므로 answer에 스택에 남아있는 빌딩의 수를 더한다.

3. 현재 빌딩을 스택에 넣는다.

이 과정을 맨 왼쪽 빌딩부터 모든 빌딩을 확인하도록 반복하면 answer에 옥상을 확인할 수 있는 빌딩 수의 합이 저장되므로 이를 출력하면 정답

풀이 설명

도시에는 N개의 빌딩이 있다. i번째 빌딩의 키가 $h_i$이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다. 그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다. 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 높거나 같은 빌딩도 포함해서 보지 못한다는 뜻이다.

이 때 각 빌딩이 확인할 수 있는 옥상 수의 합을 구해야 한다. 각 빌딩이 확인할 수 있는 옥상의 수의 합은 다시 생각해보면 각 옥상을 확인할 수 있는 빌딩의 합으로 나타낼 수 있다.

문제에서 제시한 N=6, H = {10, 3, 7, 4, 12, 2}인 경우를 확인했을 때 1번 빌딩에서 2, 3, 4번 빌딩의 옥상을 볼 수 있고, 3번 빌딩에서 4번 빌딩의 옥상을 볼 수 있고, 5번 빌딩에서 6번 빌딩의 옥상을 볼 수 있다.

이를 역으로 생각해보면 2번 빌딩의 옥상을 1번 빌딩에서 볼 수 있고, 3번 빌딩의 옥상을 1번 빌딩에서 볼 수 있고, 4번 빌딩의 옥상을 1, 3번 빌딩에서 볼 수 있고, 6번 빌딩의 옥상을 5번 빌딩에서 볼 수 있다.

즉, 빌딩에서 볼 수 있는 옥상 수의 합을 각 옥상을 확인할 수 있는 빌딩의 합으로 나타낼 수 있고 옥상을 확인할 수 있는 빌딩은 무조건 왼쪽에 있는 빌딩이기 때문에 왼쪽 빌딩부터 순서대로 확인하면 구할 수 있다.

이때 스택을 사용해 다음과 같은 순서를 반복해 옥상을 확인할 수 있는 빌딩의 합을 구할 수 있다.

1. 스택의 맨 위에서부터 확인하면서 현재 빌딩의 높이보다 큰 빌딩을 찾을때까지 스택에서 빌딩을 뺀다.

2. 이 과정에서 스택에 남은 빌딩들은 현재 빌딩의 옥상을 볼 수 있는 빌딩들이므로 answer에 스택에 남아있는 빌딩의 수를 더한다.

3. 현재 빌딩을 스택에 넣는다.

1번 과정에서 현재 빌딩의 높이보다 작거나 같은 빌딩들을 빼는 이유는 현재 빌딩의 높이보다 낮거나 같고 왼쪽에 있는 빌딩들은 현재 빌딩들에 의해서 앞으로 나올 옥상들을 보지 못하기 때문이다.

따라서 이 과정들을 거치면 answer에 옥상을 확인할 수 있는 빌딩 수의 합이 저장되고 이를 출력하면 정답이 된다.

소스 코드

fun main(){
    val br = System.`in`.bufferedReader()
    val N = br.readLine().toInt()
    val stack = IntArray(N)
    var top = -1
    var answer = 0L
    for(i in 0 until N){
        val height = br.readLine().toInt()
        while(top >= 0 && stack[top] <= height){
            top--
        }
        answer += top + 1
        top++
        stack[top] = height
    }
    println(answer)
}