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

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

프로그래머스

문제 설명

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

제한사항

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

 

정답 설명

자신의 뒤에 위치한 원소의 뒷 큰수가 자신의 뒷 큰수를 탐색하는 데 영향을 미칠 수 있는, DP 문제입니다.

구현이 어렵진 않으며, 뒤에서부터 다음과 같은 과정으로 뒷 큰수를 탐색하면 됩니다.

1. 자신의 바로 뒤에 있는 원소가 자신보다 큰 경우
   1. 자신의 뒷 큰수는 자신의 바로 뒷 원소이다.
2. 자신의 바로 뒤에 있는 원소가 자신과 같은 경우
   1. 자신의 뒷 큰수는 자신의 바로 뒷 원소의 뒷 큰수와 같다.
3. 자신의 바로 뒤에 있는 원소가 자신보다 작은 경우
   1. 뒷 원소의 뒷 큰수가 -1일 경우, 자신의 뒷 큰수 역시 -1이다. 
   2. 뒷 원소의 뒷 큰수가 자신보다 작은 경우, 자신보다 큰 원소 탐색을 위해 순차 탐색을 진행한다.
      1. 뒷 원소의 뒷 큰수가 자신보다 클 경우, 자신의 뒷 큰수 역시 뒷 원소의 뒷 큰수이다.
      2. 뒷 원소의 뒷 큰수가 -1인 경우 자신의 뒷 큰수 역시 -1이다.

자신의 뒤에 위치한 원소가 자신보다 작은 경우 결국 순차 탐색을 진행하게 됩니다. 처음엔 이 순차탐색 때문에 결국 최악의 경우에 O(n^2)의 시간이 걸릴 것으로 예상했습니다. 하지만, 자신의 뒤에 자신보다 큰 수가 없는 경우 빠른 시간 내에 뒷 큰수가 -1인 원소를 만날 수 있습니다. 예를 들어 [9, 10, 7, 8, 5, 6, 3, 4, 1, 2] 배열의 경우 10은 7의 뒷 큰수 8이 자신보다 작기 때문에 순차 탐색을 진행하여야 합니다. 하지만, 바로 다음의 8의 뒷 큰수가 -1이기 때문에 자신의 뒷 큰수 역시 -1임을 확인할 수 있습니다.

 

(처음엔 순차탐색의 경우를 방지하고자 DP의 값으로 자신의 뒷 큰수의 인덱스를 저장하였지만, 결국 인덱스 -> 배열 원소 값 으로 변환하는 시간이 필요했기 때문에 원소 값을 저장하는 시간보다 오래 걸렸습니다.)

소스 코드

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];

        answer[numbers.length - 1] = -1;
        for(int i = numbers.length - 2; i >= 0 ; i--){
            if(numbers[i] < numbers[i+1] )
                answer[i] = numbers[i+1];
            else if(numbers[i] == numbers[i+1])
                answer[i] = answer[i+1];
            else{
                int j = i+1;
                while(j < numbers.length){
                    if(numbers[i] < answer[j]){
                        answer[i] = answer[j];
                        break;
                    }
                    else if(answer[j] == -1){
                        answer[i] = -1;
                        break;
                    }
                    j++;
                }
                if(j == numbers.length)
                    answer[i] = -1;
            }
        }
        
        return answer;
    }
}