(11003) 최솟값 찾기 (Java)

문제

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를 공백으로 구분하여 순서대로 출력한다.

예제 입력 1

12 3
1 5 2 3 6 2 3 7 3 5 2 6

예제 출력 1

1 1 1 2 2 2 2 2 3 3 2 2

출처

문제를 만든 사람: baekjoon
데이터를 추가한 사람: doju

알고리즘 분류

자료 구조
우선순위 큐
덱

시간 제한

Java 8: 2.6 초
Java 8 (OpenJDK): 2.6 초
Java 11: 2.6 초
Kotlin (JVM): 2.6 초

Solution

1 시간초과

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    public static int n, l;
    public static String[] strArr;
    public static Deque<Integer> deque;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        l = Integer.parseInt(st.nextToken());

        strArr = new String[n];
        strArr = br.readLine().split(" ");

        deque = new ArrayDeque<Integer>();
        int sttIdx = 0;

        for(int i = 0; i < n; i++) {
            // 비교 대상 범위 내 첫 인덱스
            sttIdx = i-l+1 < 0 ? 0 : i-l+1;

            // 첫번째 원소는 덱에 넣어주고, 최솟값이므로 출력
            if(deque.isEmpty()) {
                deque.offer(i);
                bw.write(strArr[i] + " ");
                continue;
            }

            // 덱의 첫번째 원소가 비교 대상 범위 바깥이면 poll
            if(deque.peekFirst() < sttIdx) deque.pollFirst();

            // 새로 들어올 원소가 덱의 마지막 원소보다 작은 경우 덱의 마지막 원소 poll
            // (새로 들어올 원소보다 덱의 마지막 원소가 작은 값이 나올때까지, 이 과정에서 덱에 원소가 하나도 남지 않게되면 반복 종료)
            // > 이렇게 하면 덱 안에서는 오름차순을 유지하게 되고, 덱의 첫번째 원소가 그 비교 범위 내 최솟값이 된다.
            while(!deque.isEmpty()
                    && Integer.parseInt(strArr[i]) < Integer.parseInt(strArr[deque.peekLast()])) {
                deque.pollLast();
            }

            // 현재 원소를 덱에 offer
            deque.offerLast(i);

            // 모든 조건을 적용시킨 후 최솟값 출력
            bw.write(strArr[deque.peekFirst()] + " ");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

2

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    public static int n, l;
    public static Deque<Node> deque;
    public static class Node {
        int a, idx;
        Node(int a, int idx) {
            this.a = a;
            this.idx = idx;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        l = Integer.parseInt(st.nextToken());

        deque = new ArrayDeque<Node>();
        int sttIdx = 0;

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            // 현재 값
            int cur = Integer.parseInt(st.nextToken());

            // 비교 대상 범위 내 첫 인덱스
            sttIdx = i-l+1 < 0 ? 0 : i-l+1;

            // 첫번째 원소는 덱에 넣어주고, 최솟값이므로 출력
            if(deque.isEmpty()) {
                deque.offer(new Node(cur, i));
                bw.write(deque.peek().a + " ");
                continue;
            }

            // 덱의 첫번째 원소가 비교 대상 범위 바깥이면 poll
            if(deque.peekFirst().idx < sttIdx) deque.pollFirst();

            // 새로 들어올 원소가 덱의 마지막 원소보다 작은 경우 덱의 마지막 원소 poll
            // (새로 들어올 원소보다 덱의 마지막 원소가 작은 값이 나올때까지, 이 과정에서 덱에 원소가 하나도 남지 않게되면 반복 종료)
            // > 이렇게 하면 덱 안에서는 오름차순을 유지하게 되고, 덱의 첫번째 원소가 그 비교 범위 내 최솟값이 된다.
            while(!deque.isEmpty() && cur < deque.peekLast().a) {
                deque.pollLast();
            }

            // 현재 원소를 덱에 offer
            deque.offerLast(new Node(cur, i));

            // 모든 조건을 적용시킨 후 최솟값 출력
            bw.write(deque.peekFirst().a + " ");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

Feedback

시간초과 풀이의 경우 비교 시 매번 배열에서 index를 가지고 값을 찾아오다보니 시간초과가 발생함, 따라서 값과 index를 함께 갖고 있게하기 위해 Node 클래스를 선언하여 활용함