[JS] 프로그래머스 level.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	result
[2, 3, 3, 5]	[3, 5, 5, -1]
[9, 1, 5, 3, 6, 2]	[-1, 5, 6, 6, -1, -1]

문제풀이

첫번째 풀이

function solution(numbers) {
    var answer = [];
   
    for(let i=0; i < numbers.length; i++){
        let backnum = -1;
        for(let j=i+1; j<numbers.length; j++){
            
            if(numbers[i]<numbers[j]){
              backnum = numbers[j] 
              break;  
            } 
        }
        answer.push(backnum)
    }
    return answer;
}

결과

아무래도 반복문 두개를 사용하여 문제 해결을 하려다 보니 시간초과가 발생하였다.

두번째 풀이

function solution(numbers) {

    const length = numbers.length;
    const answer = new Array(length).fill(-1);
    const stack = [];

    for (let i = length - 1; i >= 0; i--) {
        while (stack.length !== 0 && numbers[i] >= stack.at(-1))
        stack.pop();
        if (stack.length !== 0) answer[i] = stack.at(-1);
        stack.push(numbers[i]);
    }
    return answer;
}

스택개념으로 접근하여 뒤에서부터 검사하여 뒤에 숫자와 앞에 숫자를 비교하여 접근하는 방법으로 사용하여 성공하였습니다.