백준 11003 - 최솟값 찾기

문제

시간 제한

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

N개의 수 $A_1$, $A_2$, ..., $A_N$과 $L$이 주어진다.

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

입력

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

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

출력

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

문제 풀이

N과 L의 최대 범위가 5,000,000 인 이 문제에서는 정렬 $nlog(n)$ 시간복잡도를 이용할 수는 없다고 한다. 슬라이딩 윈도우를 덱으로 구현하면 $O(N)$의 시간 복잡도로 해결할 수 있다고 하는데

먼저 덱이 무엇인지 검색해본다.

출처 : https://www.studytonight.com/java-examples/arraydeque-in-java

덱 (deque)는 양 끝에서 데이터를 삭제하거나 삽입할 수 있는 자료구조라고 한다.
앞 쪽에서 데이터를 삽입 삭제하는 메서드는 각 각 addFirst(), removeFirst()이고 뒤 쪽에서 데이터를 삽입 삭제하는 메서드는 각 각 addLast(), removeFirst()이다.

그러면 덱을 이용하여 문제를 간략하게 풀어보겠다.

예제 입력 1

1. 처음 (인덱스, 값) 형태의 클래스를 넣어준다.
(1, 1)을 넣어주면 비교 대상이 없고 범위도 만족하기 때문에 1을 출력한다.

2. (2,5)는 (1,1)과 비교했을 때 값이 크므로 덱에 추가해준다. 인덱스 범위도 1 ~ 2 이어서 만족하기 때문에 최솟값 1을 출력한다.

3. (3,2)는 (2,5)과 비교했을 때 값이 작으므로
   (2,5)를 제거해준다. 왜냐하면 가장 최솟값을 찾고 있기 때문에 (2,5)는 없어져도 무관하다.
   그리고 (1,1)과 비교했을 때 값이 크므로 덱에 추가한다. 인덱스 범위도 1 ~ 3 이기 때문에 가장 최솟값인 1을 출력한다.

4. (4,3)은 (3,2)와 비교했을 때 값이 크므로 덱에 추가한다. 이 때 인덱스 범위는 1 ~ 4 이기 때문에 3을 넘었기 때문에 (1,1) 을 제거한다. 그리고 최솟값인 2를 출력한다.

위와 같은 방법으로 코드에 적용시키면 다음과 같다.

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

class 최솟값찾기 {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
        Deque<Node> dq = new LinkedList<>();

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){

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

			// 첫번째 Node 객체를 넣는것이 아니고 Node 객체 값이 num보다 클 때
            // Deque 에 마지막 값을 삭제한다. (왜냐하면 최솟값을 찾는 것이 목표이기 때문에)
            while(!dq.isEmpty() && dq.getLast().value > num){
                dq.removeLast();
            }

            dq.addLast(new Node(i, num));

			// 만약 인덱스 범위가 벗어나면 Deque에 첫번째 Node 객체를 삭제한다.
            if(dq.getFirst().index <= i - L){
                dq.removeFirst();
            }

            sb.append(dq.getFirst().value + " ");
        }

        System.out.println(sb);

    }

    private static class Node {
        private int index;
        private int value;

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

}	

회고

처음 문제를 풀때는 객체와 deque 자료구조를 사용해야한다는 생각이 전혀 들지 않았다. 이번에도 Do it! 알고리즘 코딩테스트와 유튜브를 통해서 그나마 이해할 수 있었다. 플래니텀 문제라서 그런지 더욱 어렵게 느껴져서 문제를 내가 외우게 되는 것 같다...