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

프로그래머스

1. 문제

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

 

2. 오답

function solution(numbers) {
    const result = new Array(numbers.length).fill(-1);
    let temp = -1;
    
    for (let i=0; i<numbers.length-1; i++) {
        if (temp === numbers[i]) result[i] = result[i-1];
        else {
            for (let j=i+1; j<numbers.length; j++) {
                if (numbers[j] > numbers[i]) {
                    result[i] = numbers[j];
                    break;
                }
            }   
        }
        temp = numbers[i];
    }
    return result;
}

문제가 너무 단순해서 실행해보니 결과는 시간 초과...😂😂
제한 사항 4 ≤ numbers의 길이 ≤ 1,000,000를 생각해보면 당연한 결과였다.

3. 정답 풀이

풀이 전략

• 배열을 거꾸로 순회
• stack을 이용해 연산 횟수를 줄인다.

function solution(numbers) {
    const result = []; // 결과를 담을 배열
    let stack = []; // 비교 대상이 되는 숫자를 담을 배열
    let max = 0; // 비교를 위한 최대값
    
    // reverse 메서드로 배열을 거꾸로 순회
    numbers.reverse().forEach(num => {
        // 뒷 큰수가 없는 경우
        // result 배열에 -1 push
        // 현재 num 뒤에 뒷 큰수가 없으니, stack을 num만 남기게 초기화하고 최대값 max도 num으로 초기화한다.
        if (num >= max) {
            result.push(-1);
            stack = [num];
            max = num;
        } else {
            for (let i=stack.length-1; i>=0; i--) {
                // stack에서 num 보다 큰 수를 result 배열에 push
                // stack에 현재 수를 추가한다.
                if (stack[i] > num) {
                    result.push(stack[i]);
                    stack.push(num);
                    break;
                } else {
                    // stack의 숫자가 num 보다 같거나 작은 경우 뒷 큰수 비교에 필요 없으므로 pop으로 삭제 
                    stack.pop();
                }
            }
        }
    })
    return result.reverse()
}

 

 

 

오답 풀이에서 시간 복잡도를 줄이려고 고민하다가 시간을 너무 많이 쓴 것 같다..😅

문제가 안풀리면 같은 방법만 고집하지 말고 새로운 접근 방법을 시도하는 습관을 들여야겠다!