[백준/BOJ] 2493번: 탑

문제

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

2493번: 탑

해설

탑이 n개 있고, 이 탑들은 좌측으로 신호를 보낸다.

좌측에 현재 탑보다 더 높은 탑이 있다면 신호를 받을 수 있고, 더 높은 탑이 없다면 신호를 받을 탑이 존재하지 않는다는 의미이다.

 

문제의 예시를 보며 차근차근 알아가보자.

맨 처음 탑은 좌측에 아무 것도 없기 때문에, 신호를 받는 탑이 없다. 즉 0을 출력한다.

이제 이 탑을 스택에 넣어줄 것이다.

높이가 9인 2번 탑에서 신호를 보낸다하여도 높이가 6인 1번 탑은 신호를 받지 못한다.

또한 이후로 나올 탑이 높이가 9보다 작다면 2번 탑에서 신호를 받게 되고, 9보다 크다면, 1번 탑 또한 신호를 받을 수 없기 때문에 1번 탑은 더 이상 신경쓰지 않아도 된다.

따라서 스택에서 1번 탑의 정보를 pop하여 제거하고, 2번 탑의 정보를 넣는다.

2번 탑 또한 신호를 받을 탑이 좌측에 있지 않으므로 0을 출력한다.

3번 탑에서 신호를 보내면 2번 탑의 높이가 더 높으므로 수신할 수 있다.

또한 4번 혹은 5번에서 5보다 높이가 큰 탑이 올 수 있으므로, 2번 탑은 스택에서 제거시키지 않고, 3번 탑의 정보를 스택에 넣어준다. 2번 탑에서 수신받으므로 2를 출력해준다.

스택을 이용하여 비교하므로, 4번 탑과 가장 먼저 비교되는 것은 3번 탑이다.

이때 3번 탑은 4번 탑보다 높이가 낮으므로 신호를 수신받지 못한다. 즉, 4번 탑 이후의 탑들에게서 신호를 수신받을 일이 없다는 의미이다. 따라서 스택에서 3번 탑의 정보를 pop하여 제거해준다.

다음은 2번 탑에서 신호를 받을 수 있는지 확인한다.

2번 탑은 4번 탑보다 더 높으므로 신호를 수신할 수 있다.

스택에 4번 탑의 정보를 저장한 후, 2를 출력한다.

마지막으로, 5번 탑은 4번 탑보다 낮다. 즉, 4번 탑에서 정보를 수신하게 되므로 4를 출력하면 된다.

코드

import java.util.*

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val st = StringTokenizer(readLine())
    val sb = StringBuilder()

    val top = Stack<Pair<Int, Int>>()
    repeat(n) { i ->
        val curTopHeight = st.nextToken().toInt()

        while(top.isNotEmpty()) {
            val nextTop = top.peek()

            if(nextTop.second < curTopHeight) top.pop()
            else {
                sb.append("${nextTop.first} ")
                break
            }
        }

        if(top.isEmpty()) sb.append("0 ")
        top.add(Pair((i+1), curTopHeight))
    }

    println(sb.toString())
}