백준 6198 옥상 정원 꾸미기 Kotlin (스택)

문제 출처 : 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}인 경우

             = 
 =           = 
 =     -     = 
 =     =     =        -> 관리인이 보는 방향
 =  -  =  =  =   
 =  =  =  =  =  = 
10  3  7  4  12 2     -> 빌딩의 높이
[1][2][3][4][5][6]    -> 빌딩의 번호

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

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

입력

• 첫 번째 줄에 빌딩의 개수 N이 입력된다.(1 ≤ N ≤ 80,000)
• 두 번째 줄 부터 N+1번째 줄까지 각 빌딩의 높이가 hi 입력된다. (1 ≤ hi ≤ 1,000,000,000)

출력

• 각 관리인들이 벤치마킹이 가능한 빌딩의 수의 합을 출력한다.

알고리즘 분류

• 자료 구조
• 스택

풀이

오랜만에 스택 문제다.

스택에 빌딩이 들어올 때마다 스택의 건물들이 볼 수 있는 건물의 수를 추가해주면 된다.

 

풀이부터 말하면 스택에 i 번째 건물을 넣을때, i 번째 건물보다 작거나 같은 건물은 모두 pop하고 그 사이즈만큼 count한 다음 i 번째 건물을 push하면 된다.

 

i 번째 빌딩을 들일 때, i번째 빌딩보다 작거나 같은 스택에 있는 빌딩들은 모두 제거한다.

stk = 10,7,3이 들어있고 여기에 12가 들어온다고 생각해 보자.

10,7,3은 더 이상 앞을 볼 수 없기에 싹 밀어버리고 12만 넣는다.

 

만약 2가 들어온다면?

10,7,3이 여전히 앞을 볼 수 있기 때문에 2를 넣는다.

이때 값은 얼만큼 더해주어야 할까?

10은 7,3,2를 볼 수 있고

7은 3,2를 볼 수 있고

3은 2를 볼 수 있기 때문에 6을 더해주어야 할까?

스택에 빌딩이 들어올 때마다 건물의 수를 추가해주고 있다.

10은 이미 7,3을 본다고 추가해두었고, 7은 3을 이미 본다고 추가해 두었기 때문에

10은 2를 볼 수 있음을 추가

7도 2를 볼 수 있음을 추가

3도 2를 볼 수 있음을 추가

즉, 스택의 사이즈만큼 더해주고 스택에 2를 넣으면 된다.

 

위의 예시를 가지고 시뮬레이션해보자.

10 빌딩이 들어올 때 아직 아무 빌딩도 없다. (스택에 아무것도 없다)

stk = 10

3빌딩이 들어왔고 10빌딩보다 작기 때문에 10 빌딩이 3빌딩을 볼 수 있다. +1

stk = 10,3

7빌딩이 들어왔고 3빌딩보다 크기 때문에 3은 앞을 볼 수 없으니 제거, 10은 7을 볼 수 있으니 10,7로 유지된다. +1

stk = 10,7

4빌딩이 들어왔고 7빌딩보다 작기 때문에 10, 7빌딩은 4빌딩을 볼 수 있다. +2

stk = 10,7,4

12빌딩이 들어왔고 4,7,10 빌딩보다 크기 때문에 모두 제거

stk = 12

2빌딩이 들어왔고 12빌딩보다 작기 때문에 12빌딩은 2빌딩을 볼 수 있다. +1

stk = 12,1

끝

 

 

코드

import java.util.*
val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()

fun main() = with(System.out.bufferedWriter()){
    //input
    val stk = Stack<Int>()
    var answer = 0L
    repeat(getInt()){ _ ->
        with(getInt()){
            while(stk.isNotEmpty() && stk.peek() <= this){
                stk.pop()
            }
            answer += stk.size
            stk.push(this)
        }
    }

    write("$answer")

    close()
}