백준 11003번 문제 (최솟값 찾기) with Java

문제

11003 문제

접근법

슬라이딩 윈도우 기법을 이용해 접근했다. 우선 문제를 이해해 보면, 주어진 L 값 만큼을 범위로하여 최솟값을 찾는 문제이다. 예를 들어 예제의 경우 L이 3일 때, 0 0 1 중에 가장 작은 값, 0 1 5 중에 가장 작은 값, 1 5 2 중에 가장 작은 값, 5 2 3 중에 가장 작은 값, 2 3 6 중에 가장 작은 값(이하 생략)이렇게 총 세가지 숫자를 범위로하여 각각 최솟값을 찾는 문제다.

우선은 값을 딱 L개 정도 저장하고 있을 자료구조가 필요하다. 어차피 딱 L개의 숫자를 비교하고 그때 그때 출력하면 되니까 딱 L개 정도만 저장할 수 있으면 된다. 이 문제의 경우 Deque가 적당하다. 직관적으로 보아도 주어진 N개의 수를 차례대로대로 deque에 넣고, deque에 값이 L개 이상 찼으면 먼저 넣어진 값은 앞에서 빼주며 나중에 들어올 값은 뒤에서 넣어주면 유용하게 쓰일 것 같은 느낌이 온다.

이제 deque를 더 효율적으로 사용할 방법이 필요하다. 한 가지 컨셉이 필요한데, deque의 맨 앞에는 작은 값이오고, 뒤로 갈 수록 더 큰 숫자가 오게 하는 것이다. 이렇게 할 경우 해당 최솟값은 매번 deque의 제일 앞에 있는 숫자가 된다.

일단 한번 무식하게 생각을 해보았을 때는 아래와 같은 방법이 떠오른다.

여기서 왼쪽으로 갈수록 작은 값이 오게 하기위해, 매번 새로운 값이 들어올 때 마다 이미 들어있는 값과 비교해서 정렬을 한다. 그럼 인덱스 3 때는 아래와 같은 상황이 될 것이다.

잠시 여기서 생각해보자. 일단 여기서 하나가 더 들어올 경우 인덱스는 3일 테고, 그림은 아래와 같을 것이다.

먼저 현재 인덱스가 3이라서 인덱스 3인 박스가 들어왔다. 따라서 우리가 찾는 최솟값은 인덱스가 1,2,3 인것 중에서 찾아야 하니까 제일 먼저 들어온 인덱스가 0인 것은 빼준다. 그럼 나머지 것들 중에서 맨앞에 있는 것이 최소 값이다. 따라서 2가 최소값이다.

그런데 이 방법은, 맞긴 맞지만 루프를 돌아 새로운 값을 추가 할 때마다 매번 정렬을 해야하고, 빠져나가야 할 박스를 찾기 위해 가장 작은 index를 가진 박스를 찾아 제거해야 한다. 효율적이지 못하고, 제한시간 내에 문제를 풀지 못한다.

여기서 조금의 응용이 필요하다. 매번 정렬을 하지 말고, 그냥 새로들어올 값을 deque에 들어있는 값들과 뒤에서부터 비교해서 자신 보다 큰 값들은 뺀 후, 새로 들어올 값을 넣어도 되지 않을까? 왜냐하면, 어차피 deque에 들어갈 값이라면 deque에 함께 있을 다른 값들 보다 수명이 더 길테니까. 즉, 새로들어올 값보다 큰 값은 절대로 쓸모가 없기 때문이다.

그림을 다시 보자. 현재 deque는 이 상황이다. 이제 {값:3, 인덱스:3} 인 박스가 들어올 것인데, 정렬을 하지 말고 차례대로 넣자. 대신 자신보다 값이 큰 값이 있다면 그 것을 pop해주고 자신을 넣자. 왜냐하면, 값이 5인 박스는 무조건 뒤에 들어올 값이 3인 박스보다 먼저 소멸된다. 즉, deque에 값1, 값5인 값 두개만 있다면 값: 1인 박스가 사라질 경우 최솟값이 값 : 5가 될 수 도 있겠지만, 값 5가 deque에 존재하는 상황에서 새로들어오는 박스의 값이 5보다 작다면 5는 절대 답이 될 수 없기 때문이다. 값 :5 인 박스가 아무리 지지고 볶아도 값:5인 박스와 값:3인 박스는 함께 deque에 존재한다(게다가 값:5의 인덱스가 빠르니까 값:5 박스가 먼저 사라진다).

결국 새로들어올 값보다 더 큰 값들을 삭제하고나서 새로운 값을 넣으면, deque는 자연스럽게 정렬이 된 상태일 것이다. 아래 그림처럼.

새로운 값이 들어올 때 마다 이 알고리즘을 반복하면서 deque에 있는 가장 먼저 들어온 값, 즉 가장 먼저 들어온 값인 deque[0]의 index를 보고, 이 박스가 이제 L의 범위를 벗어나 필요없다고 판단되면 빼준다.

코드

import java.io.*;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;

public class B11003 {
    public static final Scanner scanner = new Scanner(System.in);

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

        st = new StringTokenizer(br.readLine());

        Deque<Node> deque = new LinkedList<>();
        for (int i = 0; i<n; i++) {
            int temp = Integer.parseInt(st.nextToken());

            // 새로들어올 박스의 값보다 더 큰 값이 있다면 pop해주자. 
            while(!deque.isEmpty() && deque.getLast().value > temp) {
                deque.removeLast();
            }
            deque.addLast(new Node(temp, i));
            // 너무 오래되서 빼야할 박스들을 빼는 부분
            if (deque.getFirst().index <= i -l) {
                deque.removeFirst();
            }
            bw.write(deque.getFirst().value + " ");
        }
        bw.flush();
        bw.close();
    }

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

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