뒤에 있는 큰수 찾기 (자바스크립트)

https://school.programmers.co.kr/learn/courses/30/lessons/154539

프로그래머스

문제

문제 설명

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

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

풀이

1. for문을 두번 돌려서 이후 인덱스들에 대해 검토해본다면 답이 추출되겠지만 numbers의 길이가 1백만 이하이므로 O(n^2)으로 인해 시간 초과 일어날 확률이 높음
2. 뒷 큰수를 담을 stack 을 만든다.
3. 배열을 뒤에서부터 체크해가면서 스택에 있는 값들이 현재 인덱스의 value보다 크다면 스택에는 뒷 큰수가 있는 것.
   • 스택에 있는 값들과 value를 비교할 때, 스택에 가장 큰 값인 stack[0]과 비교하는 걸로 판단.
   • 만약 stack[0]보다 작다면 뒷큰수가 존재하는 것이므로 stack 끝자락부터 비교해가기
   • 끝자락부터 비교해가면서 현재의 value보다 작은 stack에 있는 값들은 pop해주고 value를 마지막에 push
4. 만약 value가 스택에 있는 가장 큰 값보다도 같거나 크다면 뒷큰수가 없으므로 -1을 answer에 담아주고 stack에는 현재의 value만을 담아줌

function solution(numbers) {
    const n = numbers.length;
    let answer = Array.from({ length: n }).fill(-1);
    let stack = [numbers[n - 1]];
    for (let i = n - 2; i >= 0; i--) {
        if (numbers[i] >= stack[0]) {
            answer[i] = -1;
            stack = [numbers[i]];
        } else {
            if (numbers[i] < stack.at(-1)) {
                answer[i] = stack.at(-1);
                stack.push(numbers[i]);
            } else {
                while (numbers[i] >= stack.at(-1)) {
                    stack.pop();
                }
                answer[i] = stack.at(-1);
                stack.push(numbers[i]);
            }
        }
    }
    return answer;
}

const n = [9, 1, 5, 3, 6, 2];
console.log(solution(n));