뒤에 있는 큰 수 찾기

문제 유형

출처

프로그래머스

레벨

Lv. 2

문제 설명

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

제한 사항

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

문제 풀이

풀이 설명

이 문제는 제한 사항을 가장 먼저 봐야 합니다. numbers의 길이가 최대 100만이므로, 오직 단 한번의 순회(시간 복잡도 : O(n))만으로 문제를 풀 수 있어야 합니다.
따라서 이 문제를 풀기 위해 스택을 이용하는 방식으로 접근하였습니다. numbers를 순회하며 현재 숫자를 인덱스(숫자의 원 위치)와 함께 스택에 담아 두는 것과 동시에, 숫자가 담겨있는 스택을 차례로 순회합니다. 현재 숫자보다 작은 숫자가 나오는 한, 작은 숫자들의 뒷 큰수가 현재 숫자임을 알 수 있습니다. 이렇게 찾은 뒷 큰수들을 answer라는 스택에 기억 해 둡니다.(이 스택은 정답용입니다)
마지막으로 numbers 순회를 마친 후, 아직 stack에 남아있는 숫자들이 있을 수 있습니다. 아직 스택에 남아있다는 것은 뒷 큰수가 존재하지 않는 숫자들이라는 뜻입니다. 따라서 남은 숫자들의 인덱스 정보를 참고하여 answer의 해당 인덱스들은 전부 -1로 변환해 주면 됩니다. (처음에 answer를 만들 때 numbers의 길이만큼 만들어 -1로 채우고 시작하여 마지막 과정을 생략할 수도 있습니다)

풀이 코드

const solution = (numbers) => {
    const answer = [];
    const stack = [];
  
    numbers.forEach((cur, i) => {
      // stack에서 현재 번호보다 작은 숫자가 나오는 동안은 빼서 answer로 치환한다.
      while (!!stack.length && stack[stack.length - 1][0] < cur) {
        const [num, idx] = stack.pop();
        answer[idx] = cur;
      }
      // 다 뺀 후에는 현재 번호를 스택에 넣는다
      stack.push([cur, i]);
    });
  
    // 순회가 끝난 후에 스택에 남아있는 것은 -1로 변환하여 answer에 넣는다.
    stack.forEach(([num, idx]) => (answer[idx] = -1));
    return answer;
  };