[2023-04-03] 백준 11003 최솟값 찾기

[Platinum V] 최솟값 찾기 - 11003

문제 링크

성능 요약

메모리: 615552 KB, 시간: 2452 ms

분류

자료 구조, 우선순위 큐, 덱

문제 설명

N개의 수 A1, A2, ..., AN과 L이 주어진다.

Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

입력

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)

둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109)

출력

첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다.

Priority Queue를 이용한 오답

Priority Queue를 사용하여 계산하였지만 Priority Queue 내부의 poll()과 peek()의 연산 과정이 오래 걸려 fail.

import java.io.*;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] arg) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine(), " ");
        int[] A = new int[N];
        //우선순위 큐는 낮은 것부터 나감
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for(int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
            int index1 = i;
            if(!priorityQueue.isEmpty()) priorityQueue.removeIf(a -> a > A[index1]);

            if(i >= L)
                priorityQueue.remove(A[i - L]);
            priorityQueue.add(A[i]);

            bw.write(priorityQueue.peek() + " ");
        }

        bw.flush();
    }
}

DeQueue를 이용한 정답

Do it! 알고리즘 코딩 테스트 JAVA편을 참조하였다.

import java.io.*;
import java.util.*;

public class Main {
    public static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] arg) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //출력을 버퍼에 넣고 한번에 출력하기 위해 BufferedWriter 사용
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        Deque<Node> mydeque = new LinkedList<>();
        
        for(int i = 0; i < N; i++) {
            int now = Integer.parseInt(st.nextToken());
            //새로운 값이 들어올 때마다 정렬 대신 현재 수보다 큰 값을 덱에서 제거해 시간 복잡도를 줄임
            
            while(!mydeque.isEmpty() && mydeque.getLast().value > now) {
                mydeque.removeLast();
            }
            mydeque.addLast(new Node(now, i));
            //범위에서 벗어난 값은 덱에서 제거
            if(mydeque.getFirst().index <= i - L) {
                mydeque.removeFirst();
            }
            bw.write(mydeque.getFirst().value);
        }
        bw.flush();
        bw.close();
    }

    private static class Node {
        public int value;
        public int index;
        
        Node(int value, int index) {
            this.value = value;
            this.index = index;
        }
    }
}