<백준> 스카이라인 쉬운거(Gold 4)
[백준]
1863번: 스카이라인 쉬운거
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫
www.acmicpc.net
[깃허브]
ForCodeKata/baekjoon 문제집/스카이 라인 쉬운거 at main · heesoo-park/ForCodeKata
Contribute to heesoo-park/ForCodeKata development by creating an account on GitHub.
github.com
정말 쉽지 않다고 생각한 문제였다.(5랑 4랑 뭔가 느낌이 다르네;;)
스스로의 힘으로 거의 다 푼 거 같았는데 한 가지 케이스에 대한 방법이 도저히 떠오르지 않아서 완전 막혀버렸다.
스택을 써야겠다는 거는 느낌이 왔었다.
최근에 이런 문제를 풀었던 기억이 남아있었기 때문이다.
처음에는 먼저 값을 추가하고 이후에 조건을 보고 빼거나 추가하는 걸 구현했다.
그랬더니 대부분의 케이스는 통과를 할 수 있었는데 높이가 낮아질 때 0으로 낮아지지 않는 경우에 대해서 처리가 안 되더라
val cur = readln().split(' ')[1].toInt()
if (cur != 0 && stack.isEmpty()) {
stack.push(cur)
} else if (stack.peek() < cur) {
stack.push(cur)
} else if (stack.peek() > cur) {
if (cur == 0) {
while (stack.isNotEmpty()) stack.pop()
cnt++
} else if (stack.size == 1) {
stack.pop()
cnt++
stack.push(cur)
} else {
while (stack.peek() > cur) stack.pop()
cnt++
}
}위의 코드인데 stack.size == 1로 해놓은 부분을 어떻게 고쳐야할지 감이 안 오더라...
그래서 고민고민을 하다가 다른 방법을 찾아 떠났다.
그러다가 알게 된 것은 스택 내부의 값이 오름차순 정렬이 되도록 구성하면 된다는 것이었다.
정확히는 스택 내부의 top 값이 들어올 값보다 클 때 제거하는 것을 반복하여 스택에 남는 값들은 점점 증가하는 값이 되는 것이다.
사실 아직도 제대로 이해가 되지 않는다.
높이가 낮아질 때 스택에서 값이 제거되야하는 거는 그 건물의 종료점이기 때문이라고 알겠는데 그게 오름차순까지 연결되는 게 안 된다...(이해되시는 분...?)
먼저는 1차적으로 값을 쭉 받으면서 위의 과정을 진행한다.
그러고 나면 값이 쭉 오름차순으로 정렬된 것이 남거나 스택이 비어있을 것이다.
정렬된 것이 남아있다면 그 사이즈를 cnt에 저장해 값으로 출력했다.
이렇게 약간 애매모호한 상황에서 코드를 계속 만져보며 이해하려고 노력했다.
그리고 나는 참고한 곳과 달리 push하는 조건을 추가했다.
그렇게 함으로써 불필요하게 스택에 값을 추가하는 경우를 제외했다.
해당 방법으로 작성한 코드는 다음과 같다.
import java.io.BufferedWriter
import java.io.OutputStreamWriter
import java.util.Stack
val stack = Stack<Int>()
fun main() = with(System.`in`.bufferedReader()) {
val bw = BufferedWriter(OutputStreamWriter(System.out))
val n = readln().toInt()
var cnt = 0
repeat(n) {
val cur = readln().split(' ')[1].toInt()
while (stack.isNotEmpty() && stack.peek() > cur) {
stack.pop()
cnt++
}
if (cur != 0) {
if (stack.isEmpty()) {
stack.push(cur)
} else {
if (stack.peek() != cur) stack.push(cur)
}
}
}
while (stack.isNotEmpty()) {
stack.pop()
cnt++
}
bw.write("$cnt")
bw.flush()
bw.close()
}
참고)