PS(Problem Solving)/BOJ

[백준/BOJ] 2493번: 탑

JunsuKim 2022. 8. 22.

목차

728x90

문제

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

 

2493번: 탑

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1...

www.acmicpc.net

해설

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

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

 

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

[백준/BOJ] 2493번: 탑 - undefined - 해설

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

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

[백준/BOJ] 2493번: 탑 - undefined - 해설

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

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

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

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

[백준/BOJ] 2493번: 탑 - undefined - 해설

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

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

[백준/BOJ] 2493번: 탑 - undefined - 해설

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

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

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

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

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

[백준/BOJ] 2493번: 탑 - undefined - 해설

마지막으로, 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())
}
728x90

'PS(Problem Solving) > BOJ' 카테고리의 다른 글

[백준/BOJ] 10159번: 저울  (0) 2022.08.24
[백준/BOJ] 2636번: 치즈  (0) 2022.08.23
[백준/BOJ] 1082번: 해킹  (0) 2022.08.21
[백준/BOJ] 1967번: 트리의 지름  (0) 2022.08.20
[백준/BOJ] 2470번: 두 용액  (0) 2022.08.19

댓글