[백준] 18298번 : 오큰수 (Kotlin)

17298번: 오큰수

안좋은 습관이지만 해당 문제를 보고 '엥 이게 골드4..?' 라는 생각을 먼저 했습니다.

시간초과

import java.lang.StringBuilder

fun main() {
    val n = readLine()!!.toInt()
    val numbers = readLine()!!.split(" ").map { it.toInt() }.toTypedArray()
    val sb = StringBuilder()

    for (i in numbers.indices) {
        var nge = -1
        for (j in i until numbers.size) {
            if (numbers[j] > numbers[i]) {
                nge = numbers[j]
                break
            }
        }
        sb.append("$nge ")
    }
    println(sb)
}

해당 풀이로는 역시나 시간 초과가 발생했고, 시간 제한을 확인하니 1초임을 알았습니다.

---

스택을 활용하기 위해 한참 고민해 보았습니다.

나의풀이

import java.lang.StringBuilder
import java.util.Stack

fun main() {
    val N = readLine()!!.toInt()
    val numbers = readLine()!!.split(" ").map { it.toInt() }.toTypedArray()
    val sb = StringBuilder()
    val stack = Stack<Int>()

    for (i in numbers.indices) {
        // numbers[i] 왼쪽에 있는 수( =스택에 쌓여있는 인덱스)가 numbers[i]보다 작은지 한번에 검사
        // 자동으로 '가장 왼쪽에 있는 수' 조건 충족
        while (stack.isNotEmpty() && numbers[stack.peek()] < numbers[i]) {
            numbers[stack.pop()] = numbers[i]
        }
        // 위에서 검사한 numbers[i]가 오큰수가 아니라면 stack에 인덱스 추가
        stack.push(i)
    }

    // 스택에 남아있는 인덱스는 오큰수를 발견하지 못한 수
    while (stack.isNotEmpty()) {
        numbers[stack.pop()] = -1
    }
    
    numbers.forEach {
        sb.append("$it ")
    }
    
    println(sb)
}

해당 인덱스의 수마다 오른쪽으로 오큰수를 확인하는 것이 아니라 해당 인덱스의 수를 기준으로 스택에 쌓여있는 모든 인덱스와 비교하는 방법으로 해결했습니다.