[프로그래머스>Lv2] 뒤에 있는 큰 수 찾기 - Kotlin

프로그래머스

 

1. 문제

정수로 이루어진 배열 numbers가 있습니다.

배열의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰 수라고 합니다.

 

[입력]

- numbers: 정수 배열

 

[출력]

모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return

🌹 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

 

2. 풀이

먼저 자신보다 뒤에 있는 숫자에서 가장 큰 숫자를 찾는 문제이기 때문에 뒤에서부터 결과를 찾아야 합니다.

 

저는 뒷 큰수를 먼저 구하는 것이 아닌, 뒷 큰수의 index를 먼저 구해두고

마지막에 index에 해당하는 수를 numbers에서 대체하는 방식으로 구현하였습니다.

 

이렇게 하게 되면, 자신의 뒤에 있는 모든 숫자를 하나씩 탐색해가며 뒷 큰수를 찾을 필요없이,

index를 타고 가면서 빠르게 탐색할 수 있기 때문입니다.

👇🏻 요렇게!

 

3. 코드

class Solution {
    fun solution(numbers: IntArray): IntArray {
        val n = numbers.size
        val answer = IntArray(n) { 0 }
        answer[n - 1] = -1

        for (i in n - 2 downTo 0) {
            when {
                numbers[i + 1] == numbers[i] -> answer[i] = answer[i + 1]
                numbers[i + 1] > numbers[i] -> answer[i] = i + 1
                else -> {
                    var index = i + 1
                    while (index >= 0 && numbers[index] <= numbers[i])
                        index = answer[index]
                    answer[i] = index
                }
            }
        }

        return answer.map { if (it == -1) -1 else numbers[it] }.toIntArray()
    }
}​