<백준> 탑(Gold 5)

[백준]

2493번: 탑

[깃허브]

ForCodeKata/baekjoon 문제집/탑 at main · heesoo-park/ForCodeKata

제출 결과

---

 

이전에 자바로 풀어본적이 있었던 문제였다.

그래서... 잘 풀릴 줄 알았지만 다 까먹었기 때문에 또 접근방식만 떠오르고 코드로 어떻게 해야할지가 잘 모르겠더라

접근방식은 바로 스택이었다...!!

여기까지는 그냥 문제 보자마자 거의 번뜩했었다.

 

하지만 여기까지였고...

나는 처음에 탑 정보를 스택에 싹 다 넣고 하나씩 빼면서 탑 높이를 그 전 것과 비교하는 걸 생각하면서 로직을 짜보는데 그렇게 하니까 전체를 순회하는 반복문이 2개가 필요하게 됐고 그러면 시간초과에 걸리는 걸 알게 됐다.

그래서 이게 아니라는 걸 깨닫고 다른 방법을 찾았지만 떠오르지 않았다.

 

그래서 이전에 풀었던 코드를 봤더니 바로...까지는 아니고 금방 이해가 됐다.

스택에 다 넣고 시작하는게 아니라 하나씩 넣으면서 가장 위의 있는 값이 현재 위치의 탑의 높이보다 작다면 빼면서 결과 리스트에 현재 위치 값을 넣어주는 방식이었다.

이렇게 함으로써 반복문이 1개...가 아니네?! 2개를 쓰는데 되는군요?!
아마 조건을 가지고 가지치기를 해서 이게 가능했다고 생각이 든다.

 

해당 방법으로 작성한 코드는 다음과 같다.

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

fun main() = with(System.`in`.bufferedReader()) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    val n = readln().toInt()
    val result = IntArray(n) { 0 }
    val stack = Stack<Int>()
    val towers = readln().split(' ').map { it.toInt() }


    for (i in towers.size - 1 downTo 0) {
        while (stack.isNotEmpty() && towers[stack.peek()] < towers[i]) {
            result[stack.pop()] = i + 1
        }

        stack.push(i)
    }

    result.forEach {
        bw.write("$it ")
    }
    bw.flush()
    bw.close()
}