프로그래머스 - 뒤에 있는 큰 수 찾기(Greedy) / Level 2 / Java

문제 📋

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

풀이 📝

class Solution {
    public int[] solution(int[] numbers) {
        int n = numbers.length;
        int[] answer = new int[n];
        
        for (int i = 0; i < n; i++) {
            answer[i] = -1;
        }
        
        for (int i = n-2; i >= 0; i--) {
            if (numbers[i+1] > numbers[i]) {
                answer[i] = numbers[i+1];
                continue;
            }
            
            for (int j = i+1; j < n; j++) {
                if (answer[j] == -1) {
                    answer[i] = -1;
                    break;
                }
                
                if (answer[j] > numbers[i]) {
                    answer[i] = answer[j];
                    break;
                }
            }
        }
        return answer;
    }
}

1. 문제 정의
   정수 배열 numbers의 각각 원소에 대하여 자신보다 뒤에 있으면서 큰 수 들 중 가장 가까운 수를 구하는 문제이다.
   

2. 시간복잡도 계산
   numbers 배열의 크기가 최대 1,000,000이기 때문에 완전탐색으로 N^2 탐색을 할 경우 시간 초과가 날 가능성이 있다.

3. 문제 풀이
   먼저 효율적으로 탐색하기 위해 배열을 뒤에서 부터 순회하면서 i+1번째 값이 i번째 값보다 크다면 뒷 큰수를 업데이트 해줬다. 만약 작다면 -1이 나오거나 뒷 큰수를 찾을 때까지 정방향으로 배열을 순회한다.

   추가적으로 시간복잡도를 낮추기 위해 탐색 범위를 가지치기했다.
   뒷 큰수 배열의 값이 -1이면 그 뒤론 탐색을 중단하거나
   뒷 큰수를 찾으면 탐색을 중단하는 방식으로 불필요한 탐색을 줄였다.

그 결과 대부분의 테스트케이스들에서 스택을 사용한 O(N) 풀이보다 속도가 더 빠른 것을 확인할 수 있었다.

4. 예외 사항
   기타 예외 사항 없음.