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

https://school.programmers.co.kr/learn/courses/30/lessons/154539?language=java

문제

• 각 원소보다 크면서 가장 가까운 수를 '뒷큰수'라고 한다.
• 모든 수에 대한 뒷 큰수를 차례로 담은 배열을 반환하시오. 단 존재하지 않은 원소는 -1을 담는다.

제한사항

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

코드

import java.util.*;
class Solution {
    public int[] solution(int[] numbers) {
        Queue<int[]> pq = new PriorityQueue<>((a,b)-> a[0]-b[0]);
        int size = numbers.length;
        for (int i = 0; i < size; i++) {
            int cur = numbers[i];

            while(!pq.isEmpty() && pq.peek()[0] < cur) {
                numbers[pq.poll()[1]] = cur;
            }

            pq.offer(new int[] {cur,i});
        }

        while(!pq.isEmpty()) {
            numbers[pq.poll()[1]]=-1;
        }
        return numbers;
    }
}

풀이

• 제한사항이 100만이기 때문에 최대한 한 번에 해결해야 한다.
• 각 원소의 값들이 정렬되어 있지 않기 때문에 정렬을 하면서 값을 추가하는 방법이 필요했다. 따라서 정렬하면서 값들을 저장할 수 있는 PriorityQueue를 사용한다.
  • 정렬된 상태에서 가능한 이분탐색은 사용X
  • PriorityQueue의offer와poll는 O(logN)으로 해결이 가능하다.
• 만약 정렬되어 있지 않다면 이전의 모든 값들을 탐색해서 현재 원소의 값과 비교를 해야한다.
  • PriorityQueue를 사용한다면 현재 값보다 더 큰 경우에는 반복문을 멈출 수 있기 때문에 O(N^2)가 아닌 O(2N)으로 해결할 수 있다.