프로그래머스 - 뒤에 있는 큰 수 찾기

✨ Lv. 2 - 뒤에 있는 큰 수 찾기

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/154539

문제 설명

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

정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

제한사항

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

풀이 코드 + 설명

첫 풀이는 다음과 같습니다.

매번 numbers에서 shift한 현재 값을 기준으로 이보다 큰 값을 filter을 사용하여 구한 후, 가장 가까운.. 다시 말해 첫 번째 값을 result에 push 하였습니다.

function solution(numbers) {
    let result = [];
    while(numbers.length) {
        let current = numbers.shift();
        let num = numbers.filter((v) => v > current);
        if(num.length) result.push(num[0]);
        else result.push(-1);
    }
    return result;
}

다만 이렇게 구현할 경우, 시간 초과가 발생합니다. 따라서 stack을 이용하여 아래와 같은 방법으로 풀이하였습니다.

• numbers를 처음부터 순회하며 아래를 반복
• stack이 비어있지 않고 stack의 가장 위에 있는 index에 해당하는 numbers 값보다 현재 값이 더 크다면, 큰 값이 존재하는 것이므로 해당 위치의 값을 현재 값으로 변경하고 pop
• 현재 index를 stack에 push

이를 반복하면 stack에는 최종적으로 뒤에 자신보다 더 큰 숫자가 없는 index만 남게 됩니다. 이를 코드로 작성하면 아래와 같습니다.

function solution(numbers) {
    let result = new Array(numbers.length).fill(-1);
    let stack = [];
    [...numbers].forEach((v, i) => {
        while(stack.length && numbers[stack.at(-1)] < v) {
            result[stack.pop()] = v;
        }
        stack.push(i);
    });
    return result;
}