✅ 문제

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

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

✅ 풀이

이중반복문(O(N^2))을 이용한 풀이 → 테스트 20,21,22,23 시간 초과.

스택(O(N))을 이용해서 풀이해야 한다. numbers 배열을 역순으로 순회하면서 각 원소에 대해서 스택을 사용하여 뒷 큰수를 찾는다. (이 때, 각 원소는 한 번씩 스택에 푸시되고 팝되므로 모든 원소에 대해 스택 연산이 상수 시간에 이루어짐)

function solution(numbers) {
    const length = numbers.length;
  
    // 뒷 큰수가 모두 존재하지 않는 것으로 가정하고 정답 배열은 -1로 설정.
    const answer = Array.from({length}, () => -1);
    const stack = [];

    // numbers 순회
    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;
}

배열 원소에 접근할 때 앞 쪽에서부터 접근할 것인지 뒤 쪽에서부터 접근할 것인지 한번 더 생각해보자.
이중반복문으로 시간초과가 날 때, 무조건 O(N)으로 끝낼 수 있는 알고리즘을 생각해내자.