[백준] 11003번 - 최솟값 찾기 (Gold 1)

문제 링크

백준 11003번 - 최솟값 찾기 (Gold 1)

문제 설명

$N(\leq 5,000,000)$개의 수 $A_1, \cdots , A_N$와 L이 주어져 있다.
$D_i = \textrm{min}\lbrace A_{i - L + 1}, \cdots , A_i \rbrace$라고 할 때, $D_i$를 모두 출력하시오.
단, $i \leq 0$ 일 때 $A_i = \infty$으로 생각한다. 다시 말해 최솟값을 구할 때 0 이하의 첨자는 무시한다.

정답 코드 및 설명

우선순위 큐를 활용하여 풀었다. 덱(Deque)과 슬라이딩 윈도우 기법을 활용하는 또 다른 풀이도 존재하며, 이 방법의 시간 복잡도가 $O(N)$으로 더 좋다고 알려져있다. 덱을 사용하는 풀이는 블로그를 보고 알게 되었다.

우선순위 큐를 활용한 $O(N\log N)$ 풀이는 아래와 같다.
음수인 첨자들을 처리하기 위해, 배열 a[]를 L + N 크기로 만들고 맨 앞의 L개에는 무한대값을 넣는다.
그리고 우선순위 큐에 앞에서부터 (i, a[i]) 쌍을 L개를 넣어둔다.
사전 작업이 끝났으면, 다음의 과정을 i = 0부터 N - 1까지 총 N번 반복한다.

1. 우선순위 큐에 (i, a[i + L])을 넣는다.
2. 우선순위 큐의 최솟값을 가져온다. 큐 안의 원소들 간의 비교는 당연히 뒤의 원소 기준이다.
3. 최솟값의 앞의 원소, 즉 수열의 인덱스가 허용 범위 바깥이라면 우선순위 큐에서 없앤다.
4. 원하는 범위의 인덱스가 나올 때까지 반복한다.
5. 4에서 얻어진 인덱스에 해당하는 값이 $D_i$이다.

우선순위 큐의 정의만을 사용한 풀이이므로, 시간 복잡도가 $O(N \log N)$임은 자명하다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ11003 {
    int n, l;
    int[] arr;

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        l = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        arr = new int[n + l];
        for (int i = 0; i < n + l; i++) {
            if (i < l) arr[i] = Integer.MAX_VALUE;
            if (i >= l) arr[i] = Integer.parseInt(st.nextToken());
        }
    }

    void findMin() {
        StringBuilder ans = new StringBuilder();
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        for (int i = 0; i < l; i++)
            pq.add(new int[]{i - l, arr[i]});
        for (int i = 0; i < n; i++) {
            pq.add(new int[]{i, arr[i + l]});
            int minIndex = pq.peek()[0];
            while (minIndex < i - l + 1) {
                pq.poll();
                minIndex = pq.peek()[0];
            }
            ans.append(pq.peek()[1]).append(' ');
        }
        System.out.println(ans);
    }

    void solution() throws IOException {
        input();
        findMin();
    }

    public static void main(String[] args) throws IOException {
        new BOJ11003().solution();
    }
}