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

 

프로그래머스

문제 설명

정수로 이루어진 배열 ‘numbers’가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.

정수 배열 ‘numbers’가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요.

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

---

풀이 방법

나의 풀이 접근 과정

 

처음엔 이중 for문으로 풀었더니 당연히 시간 초과가 났다.

“가장 가까이에 있는 큰 수”

 

그렇다면 Stack을 써볼까?

 

for문을 뒤에서부터 돌아서 pop한 값을 가지고 다시 stack에 쌓아서 큰 수를 찾아보자 !!

필요한 Stack은 두가지였다.

• numbers를 담은 Stack
• 현재까지의 최댓값을 저장하는 Stack

 

나의 최종 소스코드

import java.util.Stack

class Solution {
    fun solution(numbers: IntArray): IntArray {
        val answer: IntArray = IntArray(numbers.size) { -1 }
        val stack: Stack<Int> = Stack() // numbers를 담은 stack
        var max: Stack<Int> = Stack() // 현재까지의 최댓값을 저장하는 stack

        numbers.forEach { stack.add(it) }

        // 배열의 끝부터 이동하면서 각 숫자에 대해 오른쪽 첫번째 큰 수를 찾는 for문
        for (i in answer.lastIndex-1 downTo 0) {
            // stack에서 숫자 하나를 꺼내(pop) 현재 숫자와 비교
            var pop = stack.pop()
            if (numbers[i] < pop) {
                // 현재 숫자가 pop한 숫자보다 작으면,
                // answer에 pop한 숫자를 저장하고 max에 pop을 다시 추가
                answer[i] = pop
                max.add(pop)
            } else {
                // 현재 숫자가 pop한 숫자보다 크면, max에서 숫자를 하나씩 더 꺼내서 비교
                while(true) {
                    if (max.isEmpty()) {
                        // max 스택이 비어버리면 answer에는 -1을 추가
                        answer[i] = -1
                        break
                    }
                    
                    pop = max.pop()
                    
                    if (numbers[i] < pop) {
                        // 현재 숫자가 pop한 숫자보다 작으면,
                        // answer에 pop한 숫자를 저장하고 max에 pop을 다시 추가
                        answer[i] = pop
                        max.add(pop)
                        break
                    }
                }
            }
        }

        return answer
    }
}

1. Stack을 선언하고 초기화 한다.
   • stack: numbers를 담은 Stack
   • max: 현재까지의 최댓값을 저장하는 Stack
2. 배열의 오른쪽 끝에서 왼쪽으로 이동하면서 각 숫자에 대해 오른쪽 첫 번째 큰 수를 찾는다.
3. stack에서 숫자를 하나 꺼내서(pop) 현재 숫자(numbers[i])와 비교한다.
4. 현재 숫자가 pop한 숫자보다 작으면, answer[i]에 pop한 숫자를 저장하고 max 스택에 pop한 숫자를 추가한다.
5. 현재 숫자가 pop한 숫자보다 크면, max 스택에서 숫자를 하나씩 꺼내어(pop) 비교한다.
6. max 스택이 비어 있으면 answer[i]에 -1을 저장하고, 반복문을 종료한다.
7. 꺼낸 숫자가 현재 숫자보다 크면 answer[i]에 해당 숫자를 저장하고, max 스택에 다시 추가한 후 반복문을 종료한다.
8. 완성된 answer 배열을 Return한다.

 

---

 

다른 풀이법

import java.util.Stack

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

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

        return answer
    }
}

1. numbers 배열의 모든 인덱스를 순회한다.
2. 스택이 비어 있지 않고, 스택의 맨 위에 있는 인덱스에 해당하는 숫자가 현재 숫자보다 작으면, 그 인덱스에 해당하는 answer 값을 현재 숫자로 업데이트 한다.
3. 스택의 맨 위 인덱스를 꺼내서(pop) 그 위치에 현재 숫자를 저장한다.
4. 현재 인덱스를 스택에 추가한다. (이 인덱스는 이후에 나오는 숫자들과 비교)
5. 완성된 answer 배열을 Return한다.
6.  

---

Comment

문제 풀이를 완료했다. 조금 어렵고 복잡하게 돌아서 푼 것 같기는 하다.

그래도 생각보다 일찍 문제를 풀 수 있어서 뿌듯하다 ><

근데 Stack을 두개를 쓰니 메모리를 너무 많이 잡아먹는다.

하나로 합쳐도 괜찮을 것 같다.