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

https://school.programmers.co.kr/learn/courses/30/lessons/154539

프로그래머스

---

 배열의 각 원소에 대해 자기보다 1) 뒤에 있고 2) 크면서 3) 가장 가까운 숫자를 "뒷 큰 수"라고 정의한다. 현재 문제는 배열이 주어졌을 때 뒷 큰 수를 구하는 문제다.

 단순히 생각해서 특정 인덱스에서 자기보다 인덱스가 높은 모든 배열 원소와 값을 비교한다면 결과를 구할 수 있다. 예를 들어 인덱스가 1이라면, 인덱스 2 ~ n-1의 원소를 모두 비교하다 보면 언젠가 답이 나오는 것이다. 이 경우 시간 복잡도는 O(n²)가 된다.

 물론 현재 문제에서는 이런 방식으로는 풀 수 없다. 4 <= numbers <= 1,000,000 조건이 걸려 있으므로 위와 같은 단순 탐색 방식으로는 최악의 경우 100만의 제곱인 1조 번의 비교 연산이 필요할 수 있으며, 따라서 비교 연산 횟수를 줄이기 위한 방법이 요구된다.

 비교 연산을 줄이기 위한 방법을 여러 가지 생각하면서 알게 된 사실은 다음과 같다.

1. 현재까지 발견한 최대값이 있는 인덱스 너머로는 탐색할 필요가 없다.
   : 최대값이 있는 인덱스 이후의 원소들은 반드시 최댓값보다 작거나 같은 값이므로 비교하더라도 의미가 없다.
2. 현재 인덱스 원소의 값이 현재까지의 최댓값보다 크다면 탐색이 필요하지 않다.
   : 현재 값이 이미 max 값보다 크기 때문에 아무리 탐색해도 더 큰 값을 발견할 수 없다. -> answer [i] = -1 이 된다.

 위 사실만으로는 [1, 1, 1, ..... , 100000] 같은 케이스는 해결할 수 없다. 마지막 인덱스를 제외한 모든 케이스에서 마지막 인덱스에 도달할 때까지 1보다 큰 값이 존재하는지 검사하기 때문이다. 이와 같은 테스트케이스라면 여전히 최악의 경우 1조에 가까운 비교 연산을 수행하게 될 수 있다.

 따라서 추가적으로 비교 연산을 줄이기 위한 방법을 찾기 위해 answer 배열에 대해 생각해 봤다. answer 배열에 담긴 값은 특정 인덱스 시점에서의 뒷 큰 수 모음이므로 numbers 배열에 비해 큰 값의 비율이 훨씬 높다. 따라서 numbers 대신 answer 배열을 순회하며 값을 찾는다면 작은 값을 무시하므로 비교 횟수를 좀 더 줄일 수 있을 것이다.

 이때 바로 뒤 인덱스의 값이 뒷 큰 수인 경우는 answer에 아직 반영되지 않은 상태이므로 현재 인덱스에서 탐색이 필요하다. 뒷 큰 수의 정의 상 바로 이전 인덱스 위치에서부터 평가할 수 있기 때문이다. 따라서 answer 배열을 탐색하기 전에 다음 인덱스의 값이 뒷 큰 수인지 먼저 판단한다. 만약 뒷자리의 값이 뒷 큰 수라면 answer 비교 없이 해당 값을 answer 배열 i 위치에 넣는다. 반대의 경우 answer 배열을 순회하며 가장 가까운 뒷 큰 수를 탐색한다.

 이런 정보를 모두 포함한 코드는 다음과 같다. 

function solution(numbers) {
    const nlen = numbers.length;
    const answer = new Array(nlen);
    answer.fill(-1);
    let midx = nlen - 1;
    for(let idx = nlen - 2; idx >= 0; idx--) {
        if(numbers[midx] > numbers[idx]) {
        // 여태까지 본 최대값이 현재 값보다 크다면 -> 나보다 큰 값 하나는 존재.
            let j = idx+1;
            if(numbers[idx] >= numbers[j]) { // 바로 뒤 값이 나보다 작거나 같음
                while(j < midx) {
                    if(numbers[idx] < answer[j]) {
                        break;
                    }
                    j++;
                }
                answer[idx] = answer[j];
            } else { // 바로 뒤 값이 나보다 큼 -> 볼것도 없음
                answer[idx] = numbers[j];
            }
        } else {
            midx = idx; // 아니면 현재 위치를 최대값으로 지정
        }
    }
    
    return answer;
}

테스트 케이스 결과

 정답률이 53%인데 6점을 받아서 신기한 문제였다.

---

 문제를 풀고 해설을 보는데, 많은 사람들이 스택을 이용하여 문제를 풀었다는 것을 알게 되었다. 이 방식도 알아보자.

 스택 기반 풀이에서는 인덱스를 앞에서 뒤로 순회한다. 스택은 인덱스 자체를 데이터로 사용하며, for문을 순회할 때마다 while문을 통해 스택의 인덱스들을 평가한다. 스택의 top에 위치한 인덱스 값을 idx라고 할 때, numbers [idx] < numbers [ i ]라면 스택에서 idx을 제거하고, answer [idx] = numbers [ i ]로 초기화한다.

 이런 동작은 현재 자기보다 작은 모든 값을 pop하는 것과 비슷하다. 특정 시점에서 numbers [ i ]의 값보다 numbers [idx]의 값이 작다는 것은 numbers [ i ]가 해당 인덱스 위치의 값들에 대해 뒷 큰 수라는 의미로, 해당 인덱스들을 제거하고 뒷 큰 수를 지정하는 것이다. numbers [ i ]가 뒷 큰 수가 아닌 값들은 numbers [ i ]보다 큰 값이라 스택에 인덱스가 남아 있거나  numbers [ i ]보다 작은 값을 뒷 큰 수로 삼아 스택에서 제거되므로 i 시점에 스택에 남는 인덱스들은 현재 제거할 수 없는 원소를 가리키게 된다.

 코드는 다음과 같다.

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

테스트 케이스 결과

 스택 기반으로 생각하면 상당히 깔끔하게 풀린다. 아직 문제를 풀 때 대응되는 자료구조가 팍 떠오르지는 않아서, 좀 더 문제를 풀어서 경험을 쌓아야겠다.