문제

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

입력

numbers : [2, 3, 3, 5]

출력

[3, 5, 5, -1]

제한 사항

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

내가 했던 풀이 방법

1. answer를 -1로 채워진 배열로 초기화해준다. (answer에 값이 변하지 않으면, 해당 수 이후에 더 큰 수는 없다는 뜻이다.)
2. stack을 빈 배열로 선언한다.
3. i를 마지막부터 0까지 역순으로 순회하면서 다음을 반복해준다.
4. stack에 요소가 추가되어 있고, 가장 상위에 있는 값이 현재 numbers의 값보다 크기 전까지 stack에 있는 값들을 하나씩 제거해준다. 해당 연산이 끝나면 stack에 상위에는 numbers의 값보다 크면서 가장 가까운 값이 들어가있게 된다. 그러므로 answer[i]에 stack의 마지막 값을 저장해준다. stack에 현재 numbers의 값을 추가해준다.
5. 모든 반복이 끝난 뒤 answer를 출력해준다.

코드

function solution(numbers) {
    var answer = Array.from({length: numbers.length},()=>-1);
    let stack = [];
    for(let i=numbers.length-1; i>=0; i--) {
        while(stack.length>0 && stack[stack.length-1]<=numbers[i]) stack.pop();
        if(stack.length>0) answer[i] = stack[stack.length-1];
        stack.push(numbers[i]);
    }
    return answer;
}

회고

역순을 생각하지 못해서 조금 삽질했다. filter를 이용해 구현을 했는데 오히려 이중 for문보다 효율이 낮아서 이중 for문으로도 구현했지만, 조금 더 좋아졌을 뿐 완벽하지는 못해서 무한 while을 이용해서 구현했다.. 하지만 가장 큰 문제인 10 1 10 10 11일 경우 1보다 큰 가장 가까운 수를 10으로 판단하게 하는 과정에서 막혔다. stack으로 풀면 된다는 것까지 왔는데 역순으로 구현하려니 stack에 저장되는거랑 내 머릿속에서 동작하는게 불일치돼서 조금 고생했다.. 오늘은 잘 안 풀리는 날인가보다..ㅜ