[programmers] 뒤에 있는 큰 수 찾기

📝 [Lv2] 뒤에 있는 큰 수 찾기

👀 문제 설명

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

 

🚨 제한 사항

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

 

💻 입출력 예

numbers	result
[2, 3, 3, 5]	[3, 5, 5, -1]
[9, 1, 5, 3, 6, 2]	[-1, 5, 6, 6, -1, -1]

 

✨ 풀이 설명

제한 사항의 길이가 길기때문에 이중 반복문으로 풀게 되면 시간초과가 난다. 
내가 생각하는 핵심은
1. 가장 가까운 큰 수를 넣는 것
2. answer에 차례대로 넣는다고 생각하지 말 것
이다.

우선, -1로 초기화한 numbers와 같은 길이의 배열을 하나 생성한다.
-1로 초기화한 이유는, 현재 숫자보다 큰 수가 뒤에 없을 경우 -1을 반환해야 하기 때문이다.
그리고 아직 큰 수를 찾지 못한 수의 인덱스를 저장할 stack이라는 빈 배열을 생성해주었다.

const answer = new Array(numbers.length).fill(-1);

  const stack = [];

 

이제 각 숫자들을 반복문을 통해 하나씩 비교한다.
만약 numbers의 인덱스가 stack의 가장 위에 있는 값인 수가 현재 숫자보다 작다면,
그 인덱스의 값은 num 보다 작다는 소리이다.
즉, 현재 비교 대상인 인덱스는 가장 최근에 적재된 수인데, num은 그와 가장 가까우면서 큰 수라는 소리이다.
이때, stack이 비어있는지도 함께 확인해 주어야 한다.
stack이 비어있다는 소리는, 현재 비교할 숫자가 앞에 있는 값들보다 작다는 소리이므로 현재 위치(인덱스)를 stack에 추가해 준다.

numbers.forEach((num, i) => {

    while (stack.length && numbers[stack[stack.length - 1]] < num) {

      answer[stack.pop()] = num;

    }

    stack.push(i);

  })

 

조금 복잡하지만 이해하면 꽤 쉽게 풀 수 있는 문제였다.
비슷한 문제로 백준의 오큰수가 있다.

 

🕵️‍♂️ 코드

function solution(numbers) {

  const answer = new Array(numbers.length).fill(-1);

  const stack = [];

  numbers.forEach((num, i) => {

    while (stack.length && numbers[stack[stack.length - 1]] < num) {

      answer[stack.pop()] = num;

    }

    stack.push(i);

  })

  return answer;

}