[프로그래머스] 뒤에 있는 큰 수 찾기 JavaScript

문제 링크

프로그래머스

 

문제 유형

스택

 

문제 풀이

처음에는 인덱스를 사용한 순회 방식을 생각해 현재 인덱스를 다음 인덱스와 차례대로 비교하면서 큰 수를 만나면 다음 인덱스를 비교하는 방식으로 구현했다. 그 결과 테스트 케이스 20~22가 시간 초과가 발생했다. 인덱스를 사용한 순회 방식으로는 해결 안되는 테스트 케이스 인 것 같아 다른 방법을 찾아보던 중 스택을 사용하라는 힌트를 발견했다. 

 

스택을 사용할 때는 다음의 사항을 고려했다.

• 가장 마지막 배열 요소부터 순회하며 스택에 추가한다. 그럼 스택에는 현재 요소 기준 뒤에 있는 숫자들만 존재하게 된다. (이러한 이점 때문에 스택에 마지막 배열 요소부터 순회하며 추가하는게 아닐까 생각이 들었다.)
• 현재 숫자에서 가장 가까운 숫자, 즉 스택의 가장 위에 있는 요소부터 비교하며 현재 숫자보다 큰 숫자를 만날 때까지 pop한다.
• 현재 숫자보다 큰 숫자를 만나게 되는 순간 결과값에 저장한다. 그 후 현재 숫자를 스택에 추가한다.

 

 

코드

function solution(numbers) {
    const stack = [];
    const result = Array(numbers.length).fill(-1);
    
    for (let i = numbers.length - 1; i >= 0; i--) {
        while (numbers[i] >= stack[stack.length - 1]) stack.pop();
        if (numbers[i] < stack[stack.length - 1]) result[i] = stack[stack.length - 1];
        stack.push(numbers[i]);
    }
    
    return result;
}