[백준] 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이다.

접근방법

왼쪽으로는 빌딩이 확인하지않으므로 뒤에서 확인하는 방식

빌딩이 볼 수 있는 갯수를 저장하는 countArr
빌딩이 막힌 빌딩이 무엇인지 알기 위한 indexArr
빌딩높이 arr이 존재

맨 뒤의 첫시작 indexArr은 buildingCount로 잡음

이후, 뒤에서부터 확인하며 막힌 빌딩이 있으면, 막힌 빌딩의 인덱스가 buildCount인 경우는 끝가지 볼 수 있는 경우이고 그게 아니면 어떤 빌딩인지 알 수 있음.
따라서 원래 지금 현재 빌딩 기준으로 내 다음 빌딩이 낮다면, 이 빌딩이 막힌 빌딩의 인덱스 높이와 비교한다. 막힌 빌딩의 높이가 현재 빌딩보다 낮으면 또 이 막힌 벽의 빌딩 높이를 확인한다.

뒤에서부터 확인하기 시작한다.
현재빌딩과 다음빌딩의 높이를 비교하고, 현재 빌딩이 더 낮다면 count[idx] = 0, index[idx] = idx + 1로 설정

다음빌딩이 더 낮다면, 다음 빌딩이 막힌 빌딩의 높이와 비교한다.
현재 빌딩이 막힌 빌딩보다 더 낮다면, 현재 빌딩의 막힌 빌딩의 index는 다음 빌딩의 막힌 빌딩인덱스이므로 index[idx] = index[index[idx+1]]이 된다.
현재 빌딩이 막힌 빌딩보다 더 크다면, 막힌 빌딩의 count를 추가로 더하고, 막힌 빌딩의 개수는 미포함되어있므로 +1 한다. 이후 또 막힌 빌딩을 막은 빌딩의 index를 확인해서 위의 과정을 반복한다.

코드

class IO6198 {
    private val br = System.`in`.bufferedReader()
    private val bw = System.out.bufferedWriter()

    fun getBuildingCount() = br.readLine().toInt()
    fun getBuildingHeight() = br.readLine().toInt()
    fun flush() = bw.flush()
    fun close() = bw.close()
    fun write(message: String) = bw.write(message)
}

fun main() {
    val io = IO6198()
    val buildingCount = io.getBuildingCount()
    val arr = Array(buildingCount) { -1 }
    repeat(buildingCount) {
        arr[it] = io.getBuildingHeight()
    }

    val countArr = Array(buildingCount) { 0 }
    val indexArr = Array(buildingCount) { -1 }
    var answer: Long = 0
    for (idx in buildingCount-1 downTo 0) {
        if (idx == buildingCount - 1) {
            indexArr[idx] = buildingCount
            continue
        }
        var recurIdx = idx + 1
        if (arr[idx] > arr[idx + 1]) {
            countArr[idx] = countArr[idx + 1] + 1

            while (indexArr[recurIdx] < buildingCount) {
                val prev = arr[recurIdx]
                val next = arr[indexArr[recurIdx]]
                if (prev <= next) {
                    if (arr[idx] > next) {
                        countArr[idx]++
                        countArr[idx] += countArr[indexArr[recurIdx]]
                        recurIdx = indexArr[recurIdx]
                    } else {
                        break
                    }
                } else {
                    break
                }
            }

            indexArr[idx] = indexArr[recurIdx]
        } else {
            indexArr[idx] = idx + 1
        }


        answer += countArr[idx]
    }
    io.write(answer.toString())
    io.flush()
    io.close()
}