[백준] 11003번 - 최솟값 찾기 (Java)(△)

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

11003번: 최솟값 찾기

 

<입력범위>

N : 수의 갯수 : 1 ~ 5,000,000

L : 수의 범위 : 1 ~ 5,000,000

 

<풀이 #1>

1. 특정 범위만큼 앞으로 이동하면서 그 범위 안에서 최솟값을 골라서 D에 저장해야 한다.

2. A[i-L+1] ~ A[i]가 범위로 주어지고, 예제 1의 L=3이라고 할 때

  A[-2] ~ A[0]의 최솟값 : 1 

  A[-1] ~ A[1]의 최솟값 : 1

  A[0] ~ A[2]의 최솟값 : 1

  A[1] ~ A[3]의 최솟값 : 2

....

3. 범위 안에서의 최솟값을 구하는 것이기 때문에 전체 배열을 오름차순으로 정렬을 하면 안된다.

4. 슬라이딩 윈도우 방식으로 L 범위만큼 이동하면서 그 범위 만큼만 배열을 복사해서 정렬을 해서 최솟값을 골라야 한다.

 

<구현 #1>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class Main {
    static int N, L;
    static int A[];
    Deque<Node> deque = new LinkedList<>();

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

	void Solve() {
        StringBuilder sb = new StringBuilder();
        int tmp[] = new int[L];
        //A[-2] ~ A[0]의 최솟값
        sb.append(A[0]+" ");
        //A[-1] ~ A[1]의 최솟값
        if (A[0] < A[1]) sb.append(A[0]+" ");
        else sb.append(A[1]+" ");
        //A[0] ~ A[3]의 최솟값부터 N까지 반복
        for (int i=0; i<N-L+1; i++) {
            //int now = A[i];
            tmp = Arrays.copyOfRange(A, i, i+L);
            Arrays.sort(tmp);
            sb.append(tmp[0]+" ");
        }
        System.out.println(sb.toString());
	}

    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        A = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
    }

    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        m.Solve();// 여기서부터 작성
    }
}

 

<Hint>

1. 슬라이딩 윈도우를 사용하는데 Deque 자료구조를 사용해서 정렬을 따로 하지 않아도 정렬 효과를 주도록 했다.

2. 값이 추가 될 때마다 deque 안에 더 큰 값이 있으면 remove를 하도록 해서 정렬이 되도록 했다.

 

<구현>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class Main {
    static int N, L;
    static int A[];
    Deque<Node> deque = new LinkedList<>();

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

	void Solve() {
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<N; i++) {
            int now = A[i];
            //1. 새로운 값 보다 마지막 값이 더 크면 반복해서 덱에서 제거한다.
            while (!deque.isEmpty()) {
                if ( deque.getLast().value > now)
                    deque.removeLast();
            }
            //2. 새 값을 마지막에 추가한다.
            deque.addLast(new Node(now, i));
            //3. 윈도우 범위를 지나간 값은 덱에서 제거한다.
            if (deque.getFirst().index <= i-L) {
                deque.removeFirst();
            }
            //4. deque의 가장 앞에 있는 값을 출력한다. 
            // 윈도우 안에서 가장 작은 값은 첫번째 값이된다.
            // 오름차순 정렬을 하지 않고도 정렬이 된다.
            sb.append(deque.getFirst().value+" ");
        }
        System.out.println(sb.toString());
	}

    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        A = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
    }

    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        m.Solve();// 여기서부터 작성
    }
}