프로그래머스 뒤에 있는 큰 수 찾기 (JS)

문제 설명

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

제한사항

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

입출력 예

입출력 예 설명

입출력 예 #1
2의 뒷 큰수는 3입니다. 첫 번째 3의 뒷 큰수는 5입니다. 두 번째 3 또한 마찬가지입니다. 5는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [3, 5, 5, -1]이 됩니다.

입출력 예 #2
9는 뒷 큰수가 없으므로 -1입니다. 1의 뒷 큰수는 5이며, 5와 3의 뒷 큰수는 6입니다. 6과 2는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [-1, 5, 6, 6, -1, -1]이 됩니다.

내풀이

첫번째 풀이

function solution(numbers) {
  // 결과 배열 -1로 채워놓고 해당하는 값만 변경
  const answer = Array(numbers.length).fill(-1); 
  for(let i=0; i<numbers.length; i++){
    for(let j=i+1; j<numbers.length; j++){
      if(numbers[i] < numbers[j]){
        answer[i] = numbers[j];
        break;
      } 
    }
  }
  return answer
}

이중반복문으로 인한 시간초과, 시간 복잡도는 O(N^2)

두번째 풀이

function solution(numbers) {
  // 결과 배열 -1로 채워놓고 해당하는 값만 변경
  const answer = Array(numbers.length).fill(-1);
  const stack = [];
  // 
  for(let i=0; i<numbers.length; i++){
    // 스택이 비어있지 않고, 스택의 마지막요소를 numbers인덱스로 넣고 numbers[i] 보다 작으면 
    while(stack.length > 0 && numbers[stack[stack.length-1]] < numbers[i]){
      // stack에서 마지막 요소로 있는 인덱스를 지우고 
      // answer에 인덱스 값을 넣고 현재 인덱스를 넣음
      answer[stack.pop()] = numbers[i]; 
    }
    // 인덱스 번호를 push
    stack.push(i) 
  }

  return answer;
}

시간 복잡도는 O(N)