[백준] 2493 탑

 

🔒 문제

 

 

🧠 아이디어

N 이 50만개므로 $$ O(N^2) $$ 으로 풀었다간 무조건 시간초과다.

50만 * 50만 => 2,500억 회 로 거진 10초가 소요된다.

 

O(N) 에 가까운 풀이를 생각해한다. ==  높이를 앞에서부터 오른쪽으로 순회하며 한 번에 답을 구할 수 있어야한다.

 

가장 먼저 신호를 받을 타워는 높이가 내 왼쪽에 있는 것중 최신의 것이므로 새로운 타워에서 신호를 보낼 때마다 다음을 검사한다.

• 새로 나온 타워가 현재 stack top 보다 낮거나 같으면
  • stack top 타워의 번호를 정답으로 입력하고
• 새로 나온 타워가 현재 stack top 보다 크면 
  • 새로 나온 타워 높이보다 낮은 모든 애들을 pop해서 지워버리고 
  • 새로나온 타워 높이와 같거나 큰 애의 타워 번호를 정답으로 입력한다.

위 분기와 상관 없이 새로 나온 타워의 높이가 어떻건 새로 마주한 타워를 스택에 넣어야한다.
(다다음 스택에 더 낮은 타워가 나타날 수 있다.)

 

타워 번호를 킵해야하므로 Stack에 단순 타워 높이 (Int) 값이 아니라 (타워 번호, 높이) 값을 keep 한다.

타워의 높이를 배열에 저장했다면 타워 번호 == index + 1 이다.

 

 

🔑 Kotlin Code

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

data class Tower(val number: Int, val height: Int) {}

fun main() {
    val bufferedReader = BufferedReader(InputStreamReader(System.`in`))
    val N = bufferedReader.readLine().toInt()
    val towerHeights = bufferedReader.readLine().split(" ").map(String::toInt)

    val stringBuilder = StringBuilder()
    val stack = Stack<Tower>()

    towerHeights.forEachIndexed { index, height ->

        // 비어져 있는 상태라면
        if (stack.isEmpty()) stringBuilder.append("0 ")
        // 최근에 세워진 타워가 바로 신호를 받을 수 있으면
        // 타워를 세우고 신호 처리.
        else if (stack.peek().height >= height) stringBuilder.append("${stack.peek().number} ")
        else {
            // 현재 나타난 타워의 신호를 받을 타워가 나타낼까지 이전 타워를 삭제시킴
            while(stack.isNotEmpty() && stack.peek().height < height) stack.pop()
            // 어떤 타워도 같거나 높은 높이를 가지지 못해 신호를 받지 못했으면 0
            if (stack.isEmpty()) stringBuilder.append("0 ")
            // 신호를 받은 타워의 번호를 추가
            else stringBuilder.append("${stack.peek().number} ")
        }

        stack.push(Tower(index + 1, height))
    }

    print(stringBuilder.toString())

}

 

 

---

⚒️ 리펙토링

매 loop 마다 스택이 비어있는지 비어있지 않은지 체크하는 것 때문에 코드가 조금 더러웠다.

아예 절대 넘을 수 없는 최대 높이의 0번 타워가 존재한다고 가정하면 더 깔끔하게 코드를 짤 수있다.

(어떤 타워든 반드시 0번 이상을 답으로 가질 것이므로)

 

새로 세울 타워의 높이와 무관하게 무조건 타워는 세울 것이고 매 loop 마다 신호를 받을 타워만 stringBuilder 에 추가해주면 된다.

 

🔑 Kotlin Code (개선된 풀이)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

data class Tower(val number: Int, val height: Int) {

}

fun main() {
    val bufferedReader = BufferedReader(InputStreamReader(System.`in`))
    val N = bufferedReader.readLine().toInt()

    val stringBuilder = StringBuilder()
    val stack = Stack<Tower>()

    // 신호를 아무 타워도 못받으면 0을 반환할 것이므로
    // 아예 높이를 무한대로 갖는 0 번 타워가 존재하는 것으로 대치
    // -> stack 이 null 인지 아닌지 검사할 필요가 없어짐. -> 코드가 간결해짐.
    stack.push(Tower(0, Int.MAX_VALUE))

    val towers = bufferedReader.readLine().split(" ").map(String::toInt)

    towers.forEachIndexed { index, currentHeight ->
        // 현재 세워질 타워에 대해 신호를 못받는 타워는 존재할 필요가 없음.
        while (stack.peek().height < currentHeight) stack.pop()
        // 신호 받은 타워가 없으면 0, 있으면 받은 타워 번호
        stringBuilder.append("${stack.peek().number} ")
        // 앞에서 신호받은 타워가 있든 없든 현재 타워는 세워야함. 타워 번호는 1부터 시작하므로 현재 index + 1
        stack.push(Tower(index + 1, currentHeight))
    }


    print(stringBuilder.toString())

}