[JAVA]백준 11003번: 최솟값 찾기

https://www.acmicpc.net/problem/11003

11003번: 최솟값 찾기

1. 문제 설명

 

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)

 

2. 풀이

 

Deque를 이용해서 풀 수 있다.

 

c++의 경우 세그먼트 트리 , 우선순위 큐를 이용해서 풀 수 있는데, Java의 경우는 불가능하다... (시간 초과 남)

 

아마, Java의 경우 입출력이 시간이 오래 걸려서 그러는 듯하다.

 

deque를 이용해서 정렬을 하여 풀 수 있다.

 

deque에는 인덱스 값과 숫자 값을 저장한다.

 

정렬을 하는 법은 간단한데, deque 뒤에서부터 deque보다 큰 값들은 모두 삭제해버리고 현재 값을 저장하면 된다.

 

Ai-L+1 ~ Ai 의 최솟값을 구하는 문제이기 때문에 deque에 이미 들어있는 값들은 현재 인덱스보다 작은 인덱스이면서 현재 값 보다 크기 때문에 최솟값 Di로 사용되지 않는다.

 

예를 들어 현재 deque에 숫자 값들이 9 10 11이 저장되어 있을 때 1이 들어오게 되면 9 10 11은 현재 인덱스 이후로 절대 Di로 사용되지 않기에 없애버려도 된다.

 

현재 값은 무조건 저장하는 이유는 그 뒤에 값들이 얼마가 나올지 모르기 때문이다. 예를 들어 현재 deque에 1 2 3 이 저장되어 있을 때 10이 들어왔다면 현재 인덱스의 최솟값은 아니지만, 뒤에 계속해서 10보다 큰 값들만 들어오게 된다면 언젠가는 10이 Di로 사용될 것이다.

 

이런 식으로, 현재 값보다 큰 값들을 제거해나가면 저절로 정렬이 될 것이다..!

 

주의해야 될 점은, 구간이 정해져 있기 때문에 구간을 벗어나는 값은 제거해 줘야 된다는 것이다.

 

구간을 벗어나는 값을 제거할 때 deque에 첫 번째 원소만 확인했는데, 이것은 우리가 이미 정렬을 했기 때문에 첫 번째 원소만 확인해도 된다.

 

정렬을 했기 때문에 첫번째 원소는 제일 처음에 deque에 들어온 값이며 제일 작은 값이다. 따라서 첫 번째 원소만 확인해도 된다!

 

처음에 많이 틀렸는데 deque empty 조건을 달지 않아서 NullPointer 에러가 났었다.

 

혹시 NullPointer가 발생하시는 분이 계시다면 deque가 비어있는데 deque 원소에 접근하지 않는지 확인해보시는 것이 좋다.

 

 

*로직

- Deque에 첫번째 값이 구간을 벗어나는지 확인. 벗어난다면 제거

- Deque에 마지막부터 현재 값보다 큰 값들 제거

- Deque에 첫번째 원소 출력

 

3. 코드

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

public class Main {

    public static Deque<Point> deque = new LinkedList<>();
    public static int N, L;


    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.addFirst(new Point(1000000001,-1));
        st = new StringTokenizer(br.readLine());


        for (int x = 0; x < N; x++) {

            int now = Integer.parseInt(st.nextToken());


            // 앞에 범위 벗어나는 것 버림

            if (!deque.isEmpty() && deque.peekFirst().idx <= x - L) {
                deque.pollFirst();
            }

            // 뒤에서부터 큰거 버림

            while (!deque.isEmpty() && deque.peekLast().num >= now) {
                deque.pollLast();
            }

            deque.addLast(new Point(now, x));


            bw.write(String.valueOf(deque.peekFirst().num) + " ");


        }

        bw.flush();




    }

    public static class Point{
        int num, idx;

        Point(int num, int idx) {
            this.num = num;
            this.idx = idx;
        }
    }



}