문제
https://www.acmicpc.net/problem/2493
2493번: 탑
첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1...
www.acmicpc.net
해설
탑이 n개 있고, 이 탑들은 좌측으로 신호를 보낸다.
좌측에 현재 탑보다 더 높은 탑이 있다면 신호를 받을 수 있고, 더 높은 탑이 없다면 신호를 받을 탑이 존재하지 않는다는 의미이다.
문제의 예시를 보며 차근차근 알아가보자.
![[백준/BOJ] 2493번: 탑 - undefined - 해설 [백준/BOJ] 2493번: 탑 - undefined - 해설](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
맨 처음 탑은 좌측에 아무 것도 없기 때문에, 신호를 받는 탑이 없다. 즉 0을 출력한다.
이제 이 탑을 스택에 넣어줄 것이다.
![[백준/BOJ] 2493번: 탑 - undefined - 해설 [백준/BOJ] 2493번: 탑 - undefined - 해설](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
높이가 9인 2번 탑에서 신호를 보낸다하여도 높이가 6인 1번 탑은 신호를 받지 못한다.
또한 이후로 나올 탑이 높이가 9보다 작다면 2번 탑에서 신호를 받게 되고, 9보다 크다면, 1번 탑 또한 신호를 받을 수 없기 때문에 1번 탑은 더 이상 신경쓰지 않아도 된다.
따라서 스택에서 1번 탑의 정보를 pop하여 제거하고, 2번 탑의 정보를 넣는다.
2번 탑 또한 신호를 받을 탑이 좌측에 있지 않으므로 0을 출력한다.
![[백준/BOJ] 2493번: 탑 - undefined - 해설 [백준/BOJ] 2493번: 탑 - undefined - 해설](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
3번 탑에서 신호를 보내면 2번 탑의 높이가 더 높으므로 수신할 수 있다.
또한 4번 혹은 5번에서 5보다 높이가 큰 탑이 올 수 있으므로, 2번 탑은 스택에서 제거시키지 않고, 3번 탑의 정보를 스택에 넣어준다. 2번 탑에서 수신받으므로 2를 출력해준다.
![[백준/BOJ] 2493번: 탑 - undefined - 해설 [백준/BOJ] 2493번: 탑 - undefined - 해설](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
스택을 이용하여 비교하므로, 4번 탑과 가장 먼저 비교되는 것은 3번 탑이다.
이때 3번 탑은 4번 탑보다 높이가 낮으므로 신호를 수신받지 못한다. 즉, 4번 탑 이후의 탑들에게서 신호를 수신받을 일이 없다는 의미이다. 따라서 스택에서 3번 탑의 정보를 pop하여 제거해준다.
다음은 2번 탑에서 신호를 받을 수 있는지 확인한다.
2번 탑은 4번 탑보다 더 높으므로 신호를 수신할 수 있다.
스택에 4번 탑의 정보를 저장한 후, 2를 출력한다.
![[백준/BOJ] 2493번: 탑 - undefined - 해설 [백준/BOJ] 2493번: 탑 - undefined - 해설](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
마지막으로, 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())
}
'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 |
댓글