프로그래머스 Lv.2 뒤에 있는 큰 수 찾기

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

접근

numbers의 길이가 1,000,000으로 이중 반복문으로 자신 뒤에 있는 모든 원소를 탐색 시 당연히 시간 초과 에러가 발생한다. 따라서 스택을 사용하거나 다이내믹 프로그래밍 방식을 사용하여 효율성을 높여야 하는데 다이내믹 프로그래밍 문제가 가장 생각해 내기 어려워 답안을 보았다. 다이내믹 프로그래밍 방식의 접근법은 뒤에 있는 원소들을 탐색하면서 원소들의 가까이 있는 수의 뒷 큰 수인 결과를 저장해 놓으며 정답을 갱신해주는 것이다.

1. 가장 가까이 있는 뒤에 수가 큰 경우 해당 숫자 저장
2. 가장 가까이 있는 뒤에 수가 작은 경우
   2-1. 가장 가까이 있는 수의 뒷 큰수가 큰 경우 가장 가까이 있는 수의 뒷 큰수를 저장
   2-2. 가장 가까이 있는 수의 뒷 큰수가 존재하지 않았을 경우 해당 원소도 뒷 큰수가 존재하지 않음

풀이

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {    
        int n = numbers.length;
        int[] answer = new int[n];
        
        Arrays.fill(answer, -1);

        for (int i = n - 2; i >= 0; i--) {
            int now = numbers[i];
            for (int j = i + 1; j < n; j++) {
                int next = numbers[j];
                if (now < next) {   // 1. 가장 가까이 있는 뒤에 수가 큰 경우
                    answer[i] = next;
                    break;
                } else {    // 2. 가장 가까이 있는 뒤에 수가 작은 경우
                    if (now < answer[j]) {
                        answer[i] = answer[j];
                        break;
                    } else if (answer[j] == -1) {
                        answer[i] = -1;
                        break;
                    }
                }
            }
        }
        return answer;
    }
}

결과