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

📜 문제

문제 링크

💡 나의 풀이

Stack을 사용해서 문제를 풀었다.

1. numbers를 순회할 때, 현재 처리하려는 것은 “이 수(number)를 뒷큰수로 가지는 숫자 구하기” 이다.
2. stack에는 이전의 인덱스 중에 아직 뒷 큰수를 찾지 못한 인덱스들이 인덱스가 큰 순으로 담겨있다. 그리고, 아직 뒷 큰수를 찾지 못한 인덱스들이 담겨있는 것이기 때문에, stack 안에 있는 원소들을 인덱스 -> numbers[인덱스]로 치환하고 봤을 때는 숫자가 작은 순으로 담겨 있다.

1. answer 배열을 -1로 초기화한다.
2. numbers를 순회한다.
   - stack이 비어있거나, number < numbers[stackTop] 인 경우 현재 수(number)의 뒷 큰수를 찾을 차례임을 의미하므로,
   stack에 현재 index를 push한다.
   - numbers[stackTop] < number인 경우 numbers[stackTop]의 뒷 큰수가 number가 된다는 것을 의미하므로
   answer 배열에 반영한다.

   🧐 PriorityQueue로 푼 풀이가 많이 보이는데 무슨 차이일까?
   PriorityQueue로 푼 풀이들을 보면, <인덱스, 값>을 원소로 두고 '값'이 작은 것을 우선으로 PriorityQueue에 넣는다.
   하지만 Stack을 사용할 경우에도 결국은 값이 작을수록 Stack Top에 가깝게 저장된다. 그 이유는 Stack Top보다 작은 값들은 이미 뒷 큰수를 찾아서 Stack에 없을 것이기 때문이다.
   따라서 Stack과 PriorityQueue가 갖는 의미에는 차이가 없다.
   PriorityQueue가 좀 더 직관적이고, 값을 넣고 뺄 때 시간 복잡도가 stack보다 좀 더 오래 걸린다는 차이가 있을 뿐이다.

⌨️ 코드

fun solution(numbers: IntArray): IntArray {
    val answer: IntArray = IntArray(numbers.size) { -1 }
    val stack = mutableListOf<Int>()

    var index = 0
    numbers.forEachIndexed { i, number -> // number가 뒷큰수가 되는 경우, answerIndex < i 여야한다.
        while (index <= i) {
            val stackTop = if (stack.isNotEmpty()) stack[stack.lastIndex] else -1

            if (stack.isEmpty() || number <= numbers[stackTop]) {
                stack.add(index++)
            } else {
                answer[stackTop] = number
                stack.removeLast()
            }
        }
    }

    return answer
}

😄 느낀 점

이 문제를 stack으로 풀 수 있을 줄은 상상도 못했다,,
2개의 pointer를 가지고 풀려고 시도했는데 안돼서 결국 질문 게시판에서 힌트를 얻어서 풀게 되었다.
stack으로 풀어내고 나서 이 문제를 어떤 관점으로 봐야 stack으로 풀어낼 생각을 바로 할 수 있을지 고민했는데, 특정 수를 뒷큰수로 가지는 것들이 규칙을 가지고 선형적으로 존재해서 한꺼번에 처리하기 위해 stack을 사용했다는 결론을 냈다. 근데 아직 이걸 바로 생각해낼 자신은 없다😅
다음으로 본 풀이는 PriorityQueue를 이용한 풀이었는데 결국 Stack과 PriorityQueue가 의미하는 바가 똑같다는 걸 느꼈는데, PriorityQueue가 좀 더 직관적으로 그 의미를 파악하기 편한 것 같다는 느낌이 들었다. 그리고 "왜 이 생각을 못했지?!?"라는 생각은 덤~!