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

문제 설명

주어진 배열에서 각 요소의 "뒤에 있는 큰 수"를 찾아야 합니다.

• "뒤에 있는 큰 수"는 현재 요소의 오른쪽에 위치한 요소 중에서 현재 요소보다 큰 값 중 첫 번째 값입니다.
• 만약 그런 값이 없다면, 결과는 -1로 표시됩니다.

예를 들어, 배열 numbers = [2, 3, 1, 5]가 주어지면 결과는 [3, 5, 5, -1]이 됩니다.

---

제한사항

• 1 ≤ numbers.length ≤ 1,000,000
• 각 요소는 1 이상 1,000,000 이하의 정수입니다.

---

해결 방법

알고리즘: 스택

1. 스택 초기화
   • 스택은 배열 내 각 요소의 값과 인덱스를 저장합니다.
   • (값, 인덱스) 형태로 저장하여 뒤에 큰 수를 효율적으로 찾습니다.
2. 배열 순회
   • 배열의 각 요소를 확인하면서 스택에 저장된 값과 비교합니다.
   • 현재 값이 스택의 최상단 값보다 크면, 해당 스택 값을 꺼내고 결과 배열을 업데이트합니다.
3. 뒤에 큰 수 없는 경우 처리
   • 결과 배열을 -1로 초기화하여 별도 처리가 필요 없게 만듭니다.
4. 결과 반환
   • 배열 순회가 끝난 후 결과 배열을 반환합니다.

---

시간 복잡도

• 스택 연산
  • 각 요소는 한 번만 스택에 추가되고, 한 번만 제거됩니다.
  • 따라서 스택 연산은 O(n)입니다.
• 총 시간 복잡도
  • 배열 순회와 스택 연산이 모두 O(n)이므로, 총 시간 복잡도는 O(n)입니다.

---

구현 코드

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

  numbers.forEach((number, index) => {
    while (stack.length > 0 && stack[stack.length - 1][0] < number) {
      const [, topIndex] = stack.pop();
      answer[topIndex] = number;
    }
    stack.push([number, index]);
  });

  return answer;
}