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

📕 문제

문제설명

정수로 이루어진 배열 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의 뒷 큰수는 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]이 됩니다.

🤔 고민과정

• 왜 뒤에서부터 비교해야할까?
  ▶ 배열을 뒤에서부터 비교하는 이유는 효율적인 처리를 위해서이다.
  가장 가까운 큰 수를 찾으려할때,
  • 앞에서부터 비교하면,
    현재 숫자보다 큰 수가 나올 때까지 뒤의 모든 숫자를 일일이 비교해야 한다.
    이는 모든 숫자에 대해 다시 모든 숫자를 비교하는 것이므로 시간 복잡도는 O(n²)
  • 뒤에서부터 비교하면,
    스택을 사용하여 이전 숫자들을 기억하면서 큰 수를 빠르게 찾을 수 있다.
    배열의 마지막 숫자부터 거꾸로 확인하면, 지금 확인한 숫자보다 큰 수는 스택에 저장되어 있고, 그 큰 수가 있는지 바로 확인할 수 있다.
    스택에 담긴 숫자들과 비교만 하면 되기 때문에 시간 복잡도는 O(n)

✅ 결과물

function solution(numbers) {
    let answer = []; // 각 숫자에 대한 가장 가까운 큰 수를 저장할 배열
    let stack = []; // 가장 가까이 있는 큰 수를 찾기 위한 비교 스택 생성

    // numbers 배열의 길이만큼 반복, 뒤에서부터 비교
    while (numbers.length) {
        // stack이 비어있는 경우: 현재 숫자가 가장 큼
        if (!stack.length) {
            answer.push(-1); // 가장 가까운 큰 수가 없으므로 -1 추가

            // 현재 숫자를 stack에 저장하고 numbers에서 제거
            stack.push(numbers.pop());
        } else {
            // stack에 값이 있는 경우, stack의 마지막 값과 현재 숫자를 비교
            if (stack[stack.length - 1] > numbers[numbers.length - 1]) {
                // stack의 마지막 값이 현재 숫자보다 크면, 해당 값을 answer에 추가
                answer.push(stack[stack.length - 1]);

                // 현재 숫자를 stack에 저장하고 numbers에서 제거
                stack.push(numbers.pop());
            } else {
                // stack의 마지막 값이 현재 숫자보다 작으면, 그 값은 현재 숫자와 비교할 필요가 없으므로 제거
                stack.pop();
            }
        }
    }

    return answer.reverse(); // 스택에 저장된 결과를 뒤집어서 반환 (원래 순서로 맞추기 위해)
}