[백준] 11003 최소값 찾기 java 풀이 (그림으로 쉬운 설명 ^^)

1. 문제 설명 📌

문제 링크

슬라이딩 윈도우에서 더 나아가서, 윈도우 구간안에 최소값을 매번 출력하는 문제이다.

2. 접근 방식 🗃️

KEY WORD: Sliding Window, Data Structure (Deque)

파이썬에서는 추가시간이 주어줘서 우선순위 큐를 이용해도 풀리지만, Java에서는 풀리지 않는다. 왜 우선순위 큐로는 안되는지에 대해 4번 항목에서 설명하겠다.

(1) 전체 접근 방식

1. ArrayDeque로 슬라이딩 윈도우를 구현한다.
   (해당 deque는 현재 구간인 값들만 가지고 있으며, 오름차순으로 값의 순서를 유지한다. (front = 최소값))
2. 슬라이딩 윈도우를 오른쪽으로 한 칸씩 움직인다.

3. 구간에 신규로 추가될 값을 A라고 쳤을 때, A와 deque의 rear(꼬리)를 비교한다
   • rear > A: A가 더 최소값이라면, rear를 deque에서 제외시킨다. (반복)
   • rear < A: A를 deque에 추가한다.
4. 현 구간에 대한 계산이 완료되었음으로, deque의 front 값을 출력한다. (현재 구간의 최소값)

(2) 그림을 활용한 해설

문제의 1,2번은 deque를 활용했다는 것만 제외하면 일반적인 슬라이딩 윈도우라서 이해에 지장이 가지 않을 것이다. 1번에서 기록한 deque의 조건 = "deque는 현재 구간인 값들만 가지고 있으면 오름차순으로 유지한다."가 왜 그런지는 차차 설명하겠다. 먼저 deque 안에는 L개 이하의 값이 저장되어 있다.만 알고 있으면 된다.

위의 그림이 슬라이딩 윈도우를 진행하기 전 초반 세팅이다. 이제 하나씩 해보자.

a. deque가 비었을 시

deque가 위 그림과 같이 비었다면 그저 현재 구간에 신규로 삽입될 값을 deque에 넣어주면 된다. 여기서는 1을 추가하게 될 것이다.

b. deque가 비어있지 않을 시

위의 접근방식 중 3번에 해당하는 시점이다. 다음으로 들어올 수는 '5'인데, 5는 1보다 큼으로, 규칙에 따라 그저 추가한다.

다음으로 들어올 수는 '2'이다. 2는 5보다 크다. 따라서 5를 deque에서 빼내고, 추가시켜야 한다.

왜 5를 빼낼까? :thinking:

5의 후임자가 되는 수 중에, 5보다 작은 수가 존재한다. 슬라이딩 윈도우를 움직일 때마다, 최좌단의 값은 빠지고, 최우단에 신규값이 추가가 된다. 따라서 5가 구간안에 살아있을 동안 후임자가 되는 값은 무조건 살아있다. 그러므로, 5가 최소값이 될 일이 없어진다. 이러한 논리에 의해 5는 필요없는 값이 되므로 빼내어준다.

2는 살아남는 이유

2는 구간이 움직이면서 '1'이란 값이 사라질 경우, 최소값이 될 수 있는 유력한 후보이기 때문이다.

이제 슬라이딩 윈도우를 움직여보자.

3은 2보다 작으니 deque에 추가된다.

6도 마찬가지 이다. 다음이 중요하다.

먼저 윈도우가 움직임에 따라 최좌단의 2는 제거된다. 이후 새로운 2가 입력된다. 최우단의 값으로 2가 추가되는 시점에서 3과 6은 쓸모없는 값이 되어버린다. 자신들이 살아있을 동안은 2가 항상 최소값이기 때문이다. 따라서 3과 6은 deque에서 제거하고 2만 살아남는다.

이런 식으로 문제를 풀면 된다. 하나 빠트린 것이 위와 같이 deque를 움직일 때마다, deque의 peek()이 최소값임으로 이를 출력해주면 된다는 것이다.

3. 코드 소개 🔎

import java.io.*;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    /*
    * 1. ArrayDeque로 슬라이딩 윈도우를 구현
    * 2. 해당 윈도우안의 값은 오름차순으로 정렬, 즉 deque의 front는 최소값을 유지
    * 3. deque의 rear와 현재 새로 삽입될 값을 비교, 만약 삽입될 값이 더 작다면, deque의 rear값 제거
    *   (why? - 이후의 값들 중 이미 자신보다 작은 값이 나왔다.
    *       == 슬라이딩 윈도우를 이동하더라도 이제 자신이 최소값일 가능성은 없다.)
    * 4. 새로 삽입될 값이 deque의 rear보다 크다면 이제 deque에 삽입
    *   (why? - 만약 front의 값이 범위를 지나쳐서 윈도우 내부에서 빠져나가면 최소값이 될 확률이 있다.)
    * */

    public static void main(String[] args) throws IOException {
        StringBuilder ans = new StringBuilder();
        int N, L;
        ArrayDeque<Num> window = new ArrayDeque<>();

        BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            if (window.isEmpty()) window.add(new Num(i, Integer.parseInt(st.nextToken())));
            else {
                int now = Integer.parseInt(st.nextToken());
                if(window.peek().i <= i-L){window.poll();}

                while (!window.isEmpty()&& window.peekLast().v > now) window.pollLast();
                window.add(new Num(i, now));
            }
            ans.append(window.peek().v).append(" ");
        }
        System.out.println(ans);
    }
}

class Num {
    int i;
    int v;

    public Num(int i, int v){
        this.i = i;
        this.v = v;
    }
}

4. 배운 것들 🎯

오랜만에 deque를 사용하려하니, 명령어가 헷갈렸다. java 명령어가 front와 rear로 구분되어 있으면, 빠르게 다시 이해했을텐데 first와 last로 명령어를 구분해놔서, 'deque의 front에 넣으려면 무슨 명령어를 써야하지?' 라는 생각에 헤멨다. 그래서 정리하려고 한다.

queue도 마찬가지지만, deque도 꼬리로 입력이 들어와서 머리로 출력되는 선입선출(먼저 들어간 것이 먼저 나오는) 구조 이다.

각각을 first와 Last라고 부른다.

원래 queue의 성질에 따라 자연스럽게 (꼬리에 값을 집어넣고, 머리것을 출력) 사용하고 싶다면, queue와 같은 일반적인 명령어로 가능하다. 하지만 deque만의 성질을 사용하고 싶다면, (머리로 값을 집어넣고, 똥꼬에서 빼내는) 위와 같이 first나 Last를 명명해줘야 한다.