프로그래머스 - 뒤에 있는 큰 수, 백준 - 오큰수 [Kotlin]

[문제]

정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.
정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

 

[입력 조건]

numbers의 길이는 4보다 크거나 같으며, 백만보다 작거나 같다. 

각 number의 값은 1보다 크거나 같으며 백만보다 작거나 같다. 

 

[해설]

배열을 순회하며, 현재 인덱스의 뒤큰수를 찾는것이 아닌, 현재 배열의 값을 뒤큰수를 가지는 인덱스를 찾는 것이 핵심이다.

스택을 활용하여, 현재 배열의 값을 뒤큰수로 가지는 값을 찾을 수 있다. 

스택에 배열의 값을 삽입하기 전, 스택의 마지막 값보다 현재 배열의 값이 더 작다면, 스택의 마지막 값의 뒤큰수가 될 수 없다. 

따라서 그대로 스택에 삽입하며, 자연스럽게 스택은 내림차순의 형태를 띈다. (마지막 값을 활용하는 이유도, 스택에서 가장 작은 값이기 때문이다.)

만약 스택의 마지막 값보다 현재 배열의 값이 더 크다면, 스택의 마지막 값의 뒤큰수는 현재의 값이 된다. 또한, 마지막 값뿐만 아니라 while문을 통해, 스택의 값중 현재 배열의 값보다 작은 수는 모두 현재 배열의 값을 뒤큰수로 가진다. 뒤큰수를 찾은 값은 스택에서 제외한다. 

 

Do it 알고리즘 코딩테스트 해설 풀이

 

풀이한 코드 : 뒤에 있는 큰 수 

class Solution {
    fun solution(numbers: IntArray): IntArray {
        val stack = mutableListOf<Int>()
        val result = IntArray(numbers.size){ -1 }
        for(i in numbers.indices){
            while(stack.isNotEmpty() && numbers[i] > numbers[stack.last()]){
                result[stack.last()] = numbers[i]
                stack.removeLast()
            }
            stack.add(i)
        }
        return result
    }
}

 

풀이한 코드 : 오큰수

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer

fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    val stk = StringTokenizer(br.readLine())
    val numbers = IntArray(n)
    repeat(n){ i ->
        numbers[i] = stk.nextToken().toInt()
    }
    val stack = mutableListOf<Int>()
    val result = IntArray(numbers.size){ -1 }
    for(i in numbers.indices){
        while(stack.isNotEmpty() && numbers[i] > numbers[stack.last()]){
            result[stack.last()] = numbers[i]
            stack.removeLast()
        }
        stack.add(i)
    }
    print(result.joinToString(" "))
}