백준 [2493] kotlin

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

2493번: 탑

 

[풀이]

stack을 이용하여 풀면 편하다.

왼쪽 방향으로 이동하면서 인접한 탑끼리 비교를 한다. 

2가지 경우로 나눌 수 있다.

 

1. i번째 탑이 i-1번째 탑의 높이보다 큰 경우

이러한 경우에는 i 번째에서 레이저 신호를 보내도 i-1에서 받을수가 없다.

따라서 Pair를 이용하여, i번째의 인덱스값과 높이를 stack에 저장을 한다.

 

2. i번째 탑이 i-1번째 탑의 높이보다 작거나 같은 경우

이 경우는 i번째에서 보낸 신호가 i-1에서 받을 수 있게 되므로,

정답을 기록하는 ans 배열에 i번째에 i를 기록한다 (인덱스는 0부터 시작하므로 i-1에 +1이 되어 i가 된다)

그리고 stack에 저장된 탑들은 i보다 큰 탑들이 저장되어 있으므로, while 문을 통해 반복하여 비교해준다

peek를 통해 가장 최근에 저장된 탑의 정보를 가져와서, i-1번째 타워와 비교를 해주어 수신이 가능한지 체크를 한다.

만약 수신이 가능하면, pop을 통해 제거를 해주고 불가능이라면,  while문을 빠져나온다.

 

[코드]

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.Stack

fun main()
{
    var br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.`out`))

    var N = br.readLine().toInt()
    var top = br.readLine().split(" ").map {it.toInt()}

    var st = Stack<Pair<Int, Int>>()
    var ans = IntArray(N,{0})
    for(i in N-1 downTo 1)
    {
        if(top[i] > top[i-1]){
            st.add(Pair(i,top[i]))
        }
        else{
            ans[i] = i
            while(st.isNotEmpty())
            {
                val pd = st.peek()
                if(pd.second < top[i-1]){
                    st.pop()
                    ans[pd.first] = i
                }
                else break
            }
        }
    }
    bw.write(ans.joinToString(" "))
    bw.flush()
    bw.close()
}