[BOJ 골드4] 탑 보기 22866번 Kotlin

문제

설명

• 전에 카카오 문제중에 건물 비슷한 문제가 있었는데 못푼경험이 있어 스택문제라는 것을 떠올렸다
• 풀이 과정은 크게 3단계로 나눌 수 있는데 현재 건물에서 좌측에 볼 수 있는 건물을 먼저 구하고 우측에 볼 수 있는 건물을 뒤쪽부터 순회하며 구하고 이 과정에서 가장 가까운 건물을 저장하는 것이 문제의 핵심이다.

코드

import java.lang.Math.abs
fun main() = with(System.`in`.bufferedReader()){
    readLine()
    val height = readLine().split(" ").map{it.toInt()}
    val ans = MutableList(height.size){MutableList(2){0} }
    var st = mutableListOf<Pair<Int,Int>>()
    val save = MutableList(height.size){Int.MAX_VALUE}
    for(i in height.indices){
        while(!st.isEmpty()&&st.last().first<=height[i]){
            st.removeLast()
        }
        ans[i][0] += st.size
        if(!st.isEmpty()&&abs(i-st.last().second)<save[i]){
            ans[i][1] = st.last().second+1
            save[i] = abs(i-st.last().second)
        }
        st.add(Pair(height[i],i))
    }
    st.clear()
    for(i in height.indices.reversed()){
        while(!st.isEmpty()&&st.last().first<=height[i]){
            st.removeLast()
        }
        ans[i][0] += st.size
        if(!st.isEmpty()&&abs(i-st.last().second)<save[i]){
            ans[i][1] = st.last().second+1
            save[i] = abs(i-st.last().second)
        }
        st.add(Pair(height[i],i))
    }
    ans.forEach{
        if(it[0]>0) {
            println("${it[0]} ${it[1]}")
        }
        else{
            println(0)
        }
    }
}