17298번: 오큰수

문제 출처 : https://www.acmicpc.net/problem/17298

17298번: 오큰수

언어 : Kotlin

 

문제 설명 :

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

• 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
• 총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 512MB

 

입출력 예 :

입력	출력
4 3 5 2 7	5 7 7 -1
4 9 5 4 8	-1 8 8 -1

시간 초과로 실패한 풀이 : 

import java.io.BufferedWriter
import java.io.OutputStreamWriter

fun main() = with(System.`in`.bufferedReader()) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val n = readLine().toInt()
    val arr = readLine().split(" ").map { it.toInt() }
    val dp = Array(n) { 0 }

    for (i in arr.indices) {
        var max: Int
        try {
            for (j in i + 1 .. n) {
                max = arr[j]
                if (arr[i] < max) { dp[i] = max; break } else dp[i] = -1
            }
        } catch (_: Exception) {
            dp[dp.lastIndex] = -1
        }
    }

    bw.write(dp.joinToString(" "))
    bw.flush()
    bw.close()
}

중첩 반복문으로 시간초과가 난 것 같다.

 

 

풀이 : 

import java.io.BufferedWriter
import java.io.OutputStreamWriter
import java.util.*

fun main() = with(System.`in`.bufferedReader()) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val n = readLine().toInt()
    val arr = readLine().split(" ").map { it.toInt() }.toMutableList()
    val stack = Stack<Int>()

    for (i in arr.indices) {
        while (stack.isNotEmpty() && arr[stack.peek()] < arr[i]) { arr[stack.pop()] = arr[i] }
        stack.push(i)
    }

    while (stack.isNotEmpty()) { arr[stack.pop()] = -1 }

    bw.write(arr.joinToString(" "))
    bw.flush()
    bw.close()
}