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

https://school.programmers.co.kr/learn/courses/30/lessons/154539?language=javascript

프로그래머스

 

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

제한사항
4 ≤ numbers의 길이 ≤ 1,000,000
1 ≤ numbers[i] ≤ 1,000,000

 

직관적인 방법으로는 하나당 전체 탐색하여 최악의 경우 시간 복잡도가 높을 것이라 보고 여러 방안을 탐색했지만 풀 수 없었다.

 

아래는 해답을 찾다 가장 직관적이고 풀이를 잘 설명한 분의 코드이다.

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

  for (let i = 0; i < numbers.length; i++) {
    //stack이 비어져있지 않고 현재 숫자보다 작은 숫자가 있는 경우 반복한다.
    while (stack.length && numbers[stack[stack.length - 1]] < numbers[i]) {
      //스택에서 인덱스를 하나씩 꺼내서 해당 인덱스의 값을 numbers[i]로 바꿔서 뒤에 있는 큰 수를 찾는다.
      answer[stack.pop()] = numbers[i];
      //이를 반복하면서 스택에 남아있는 인덱스들에 대해서도 뒤에 있는 큰 수를 찾아낸다. 
    }
    stack.push(i);
  }
  return answer;
};

 

 

작동 원리

1. 초기화:
   • 결과를 저장할 answer 배열을 -1로 초기화합니다.
   • 스택 stack은 인덱스를 저장합니다.
2. 순차 탐색:
   • 배열 numbers를 한 번 순회하면서 현재 숫자보다 작은 숫자가 스택에 있을 경우, 반복적으로 처리합니다.
   • 현재 인덱스 i의 값 numbers[i]를 이용해 스택의 인덱스에 해당하는 값과 비교:
     • 스택의 마지막 인덱스 stack[stack.length - 1]에 해당하는 값이 numbers[i]보다 작다면, 큰 수를 찾은 것이므로:
       1. 스택에서 인덱스를 꺼냅니다 (stack.pop()).
       2. answer 배열의 해당 위치에 numbers[i]를 저장합니다.
   • 현재 인덱스 i를 스택에 추가합니다.
3. 결과 반환:
   • 모든 숫자를 처리한 후에도 스택에 남아 있는 인덱스들은 뒤에 더 큰 수가 없는 숫자들이므로, 초기값 -1이 유지됩니다.
   • 최종적으로 answer 배열을 반환합니다.

---

시간 복잡도

• 최악의 경우: O(n)
  • 각 원소는 스택에 한 번 추가되고, 한 번 제거됩니다.
  • numbers 배열의 길이를 n이라 할 때, 스택의 연산은 총 2n번 수행되므로 시간 복잡도는 O(n)입니다.

---

공간 복잡도

• 스택:
  • 최대 nnn개의 인덱스를 저장할 수 있으므로, 스택의 공간 복잡도는 O(n)입니다.
• 결과 배열:
  • 결과를 저장하는 answer 배열도 크기가 n이므로 O(n)입니다.

따라서, 공간 복잡도는 O(n)입니다.