백준 - 6198 옥상 정원 꾸미기 (코틀린)

[문제]

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

6198번: 옥상 정원 꾸미기

[코드]

import java.util.*

private var n = 0
private lateinit var arr : LongArray
private lateinit var stack: Stack<Long>

fun main() {
    val br = System.`in`.bufferedReader()
    n = br.readLine().toInt()
    arr = LongArray(n){0}
    stack = Stack()
    stack.push(Long.MAX_VALUE)
    var cnt :Long = 0
    repeat(n){
        val cur = br.readLine().toLong()
        while(stack.peek() <= cur)
            stack.pop()
        cnt += (stack.size -1)
        stack.push(cur)
    }
    println(cnt)
}

[풀이]

스택을 이용해서 풀었다.

높이가 1,000,000,000까지 이므로 Long 을 쓰고

스택에 Long 최댓값을 넣어준다.(처음 비교할 때 예외처리를 안하기 위해서)

스택에는 입력값보다 큰 높이들이 들어간다.

값을 입력받을때마다 while문을 통해 스택의 최상단 값과 입력값을 비교하는데 만약 입력값이 스택 최상단 값보다 크거나 같으면 정원을 못 보기 때문에 pop연산을 해준다.그리고 스택의 최상단값이 입력값보다 커질 때까지 반복한다.

 

정원을 볼 수 있는 건물 갯수를 누적하여 더한값을 cnt로 하고

스택에는 입력값보다 큰 높이들이 있기 때문에 cnt에 누적 합산을 하는데

스택에 Long 최댓값이 있으므로 스택 크기에서 1을 빼준 값을 누적 합산을 한다.

이후에 스택에 입력값을 추가한다.

 

Github : https://github.com/eshc123/2021AlgorithmStudy/blob/main/src/main/PS/baekjoon/6198.kt