(Javascript) 뒤에 있는 큰 수 찾기

 

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

 

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

 

---

처음엔 가장 단순하게, numbers를 앞에서부터 순회하며 numbers를 현재 인덱스 i 이후로 자른 뒤, 현재 값 e보다 큰 값만을 filter해서 가장 앞의 원소를 반환하기로 했다.

function solution(numbers) {
    var answer = [];
    
    numbers.map((e, i) => {
    	var min = numbers.slice(i).filter((n) => n > e))[0];
        return !min ? -1, min;
    });
    return answer;
}

 

 

 이대로 풀렸다면 좋았겠지만 당연하게도 시간초과가 떴다.

 위 코드의 시간복잡도를 생각해보면, 먼저 map으로 순회하면서 n, filter로 한번 더 순회하면서 n^2이 된다.

 numbers의 길이가 최대 100만개 이므로, n^2의 시간복잡도로는 문제를 풀 수 없었다.

 

 이후로 어떻게든 시간복잡도를 줄여보고자 filter 대신 직접 순회하며 큰 수를 찾는 즉시 반환하는 등 코드를 수정했지만, 문제를 풀 수 없었다.

 

 

 

 도무지 해답을 알 수 없어서 문제를 검색해보았다.

 

 문제는 numbers를 뒤에서부터 순회하며 스택을 이용해 큰 수를 찾는 과정을 최적화하여 풀 수 있었다.

 

0. answer를 길이가 numbers.length이고 초기값이 -1인 배열로 초기화한다.

1. stack을 준비한다.

2. numbers를 뒤에서부터 앞으로 순회한다.

3. 현재 인덱스의 값이 스택의 top 값보다 크다면 스택을 pop한다.

4. 더이상 pop할 수 없을때까지 반복한다.

5. 만약 스택이 비어있지 않다면 answer의 현재 인덱스에 스택의 top 값을 넣는다.

6. 스택에 현재 인덱스의 값을 넣는다.

 

 이 풀이는 numbers를 뒤에서부터 순회하면서 stack에 차곡차곡 쌓는데, 그 과정에서 한번씩 스택을 정리해주는게 포인트다.

 예를 들어 입력이 [2, 3, 3, 5]인 경우, 맨 뒤의 원소인 5를 스택에 넣는데, 먼저 스택을 정리한다. 스택이 비어있으므로 answer는 [-1, -1, -1, -1] 그대로이고, stack에는 [5]만 들어있다.

 다음으로 2번 원소인 3을 스택에 넣는데, 먼저 스택을 정리한다. 스택의 top이 5인데, 이는 3보다 큰 수이므로 answer[2] = 5이고, answer는 [-1, -1, 5, -1]이 된다. 스택에는 [5, 3]이 들어있다.

 1번 원소인 3을 스택에 넣기 전에 스택을 정리한다. 스택의 top이 3인데, 이는 3과 같으므로 pop한다. 다음 스택의 top은 5인데, 이는 3보다 큰 수이므로 answer[1] = 5이고, answer는 [-1, 5, 5, -1]이 된다. 스택에는 [3, 5]가 들어있다.

 0번 원소인 2를 스택에 넣기 전에 스택을 정리한다. 스택의 top이 3이고, 이는 2보다 큰 수이므로 answer[0] = 3이 된다. answer는 [3, 5, 5, -1]이 된다. 스택은 [5, 3, 2]가 된다.

 

 stack에 쌓이는 수를 잘 살펴보면 항상 큰 수부터 작은 수까지 내림차순으로 정렬된다. 왜냐면 어떤 수를 스택에 넣을 때, 그 수보다 큰 수가 나올때까지 스택을 pop하기 때문이다.

function solution(numbers) {
    var answer = new Array(numbers.length).fill(-1);
    var stack = [];
    
    for(var i = numbers.length - 1; i >= 0; i--){
        while(stack.length > 0 && stack[stack.length - 1] <= numbers[i]) stack.pop();
        if(stack.length > 0) answer[i] = stack[stack.length - 1];
        stack.push(numbers[i]);
    }
    return answer;
}