문제

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

제한 사항

• 4 ≤ numbers의 길이 ≤ 1,000,000
  • 1 ≤ numbers[i] ≤ 1,000,000

풀이

아이디어 (시간초과 ver)

• 문제의 뜻 그대로, numbers를 순회하면서 해당 숫자 뒤에 있는 모든 수 중에서 Array.prototype.findIndex() 함수를 통해서 해당 수보다 큰 첫 번째 수의 인덱스를 받아내는 로직을 작성하였다.
• 하지만, numbers의 최대 길이가 백만이므로, 저렇게 했다가는 O(N^2)이 되어서 시간 초과가 날 게 분명했는데도 그래도 한 번 해 봤다.

function solution(numbers) {
    var answer = [];
    while(numbers.length) {
        const cur = numbers.shift();
        const idx = numbers.findIndex(n => n > cur);
        answer.push(idx !== -1 ? numbers[idx] : -1);
    }
    
    return answer;
}

정답 풀이

• 문제에서 뒷큰수의 정의를, 자신보다 크면서 **가장 가까이 있는 수**를 뒷 큰수라고 합니다.라고 하였다. 여기에서 뭔가 스택의 냄새를 맡으면(?) 된다.
• 스택을 어떻게 사용하느냐. numbers를 순회하면서 계속 스택에 쌓다가, 현재 숫자와, 스택에 있는 수를 비교했을 때, 현재 숫자(n)가 더 크다면, 현재 숫자보다 더 큰 값을 스택에서 만날 때까지 스택을 pop 해준다. pop 해주면서 이 때 answer 배열의 알맞은 자기의 인덱스에 n을 써 넣는다.
  (answer 배열은 numbers 배열의 길이만큼 선언하고 -1로 모두 채워서 초기화한다.)

function solution(numbers) {
    var answer = new Array(numbers.length).fill(-1);
    var stack = [];
    
    numbers.forEach((n, idx) => {
        let backtrackIdx = stack.length - 1;
        while(backtrackIdx >= 0 &&  n > stack[backtrackIdx][0]) {
            let elem = stack.pop();
            answer[elem[1]] = n;
            backtrackIdx--;
        }
        stack.push([n, idx]);
    })
    
    return answer;
}

파이썬 코드

• 같은 풀이이지만 파이썬이 음수 인덱스도 지원하기 때문에 훨씬 간결함..!

def solution(numbers):
    stack = []
    answer = [-1 for _ in numbers]
    for i, num in enumerate(numbers):
        while stack and stack[-1][0] < num:
            val, idx = stack.pop()
            answer[idx] = num
        stack.append([num, i])
    
    return answer