[백준] 11003번 : 최솟값 찾기 - C++ / JAVA

백준 11003 : 최솟값 찾기

등급 : Platinum V

11003번: 최솟값 찾기 (acmicpc.net)

11003번: 최솟값 찾기

사용 알고리즘 : Sliding Window

사용 자료구조 : Priority_Queue, Deque

 

이 문제는 두 가지 방법으로 풀 수 있다.

 

  1. 우선순위 큐를 이용한 방법 (C++ 통과, JAVA 시간초과)

       우선순위 큐에 값과 인덱스를 같이 넣고, 최솟값이 유효한 인덱스에 있는지를 확인하여 출력.

       다음과 같이 값이 들어오고, 슬라이딩 윈도우의 크기가 3이라고 하자.

       현재 위치의 값을 우선순위 큐에 입력하고, 우선순위 큐의 TOP을 출력한다.

         ( 이때 우선순위 큐는 인덱스와 상관없이 값에 따라 정렬된다 )

       3번 인덱스까지 진행 된 상황을 살펴보면, 우선 순위 큐는 위와 같다.

       이때, TOP에 있는 값은 현재 조사하는 인덱스인 1~3에 속하지 않으므로 POP해준다.

       이후 다음 TOP의 인덱스를 확인하고, 해당 범위 안에 들어가면 TOP을 출력한다.

 

       이와 같은 방식으로 쉽게 구현할 수 있다.

<hide/>
#include <iostream>
#include <queue>

using namespace std;

priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> pq;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, l, x;
    cin >> n >> l;
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        pq.push({ x, i });
        while (pq.top().second < i - l + 1) pq.pop();
        cout << pq.top().first << " ";
    }
}

<hide/>
// TLE 발생 코드
import java.io.*;
import java.util.*;

public class Main {
    static class pair
    {
        int idx;
        int value;

        pair(int idx, int value)
        {
            this.idx = idx;
            this.value = value;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int l = Integer.parseInt(st.nextToken());
        PriorityQueue<pair> pq = new PriorityQueue<>((p1, p2)->{
           return p1.value - p2.value;
        });

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++)
        {
            pq.add(new pair(i, Integer.parseInt(st.nextToken())));

            while(pq.peek().idx < i - l + 1) pq.poll();
            sb.append(pq.peek().value).append(" ");
        }
        System.out.println(sb);
    }
}

 

 

  2. 덱의 Monotone Queue Technique을 이용한 방법

       슬라이딩 윈도우 기법을 이용한 덱 최적화로 풀이.

       덱을 알아서 오름차순 정렬이 되도록 구현.

       덱이 비어있을 경우 현재 위치의 인덱스와 값을 넣는다.

     

       덱의 첫 값의 인덱스가 슬라이딩 윈도우의 범위 밖이라면 POP, 그렇지 않다면 유지한다.

       현재 위치(1번 인덱스)의 값과 덱의 끝의 값을 비교한 후, 현재 위치의 값이 더 크거나 같으면 그대로 입력한다.

       마찬가지로 덱의 첫 값의 인덱스가 슬라이딩 윈도우의 범위 밖이라면 POP, 그렇지 않다면 유지한다.

       현재 위치(2번 인덱스)의 값(2, 2)과 덱의 끝의 값(1, 5)을 비교했을 때, 덱의 끝 값보다 현재 위치의 값이 더 작다.

       이때, 덱의 끝 값이 현재 값과 같거나 더 작을 때까지 끝 값을 빼주도록 한다. ( (1, 5) POP ) 

        → 이 값들은 최솟값이 될 후보가 될 수 없기 때문이다.

             위의 방법대로 덱을 유지하면, 덱이 최대 크기를 가질 때는 오름차순 정렬이 되었을 때이며, 그 크기는 윈도우의 크기와 동일

             즉, 덱 안에 있는 수보다 더 작은 값이 나오게 된다면 이보다 큰 덱 내부의 값들은 의미가 없어진다.

       덱의 첫 값의 인덱스(0, 1)가 슬라이딩 윈도우의 범위 밖이므로 POP 해준다.

       현재 위치(3번 인덱스)의 값과 덱의 끝의 값을 비교했을 때, 덱의 끝 값보다 현재 위치의 값보다 크므로 그대로 입력.

<hide/>
#include <iostream>
#include <deque>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    deque <pair <int, int>> d;
    int n, l, x;
    cin >> n >> l;
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        if (!d.empty() && d.front().second < i - l + 1) d.pop_front();
        while (!d.empty() && d.back().first > x) d.pop_back();
        d.push_back({ x, i });
        cout << d.front().first << " ";
    }
}

<hide/>
import java.io.*;
import java.util.*;

public class Main {
    static class pair
    {
        int idx;
        int value;

        pair(int idx, int value)
        {
            this.idx = idx;
            this.value = value;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int l = Integer.parseInt(st.nextToken());
        Deque<pair> d = new ArrayDeque<>();

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++)
        {
            int x = Integer.parseInt(st.nextToken());
            if(!d.isEmpty() && d.peekFirst().idx < i - l + 1) d.pollFirst();
            while(!d.isEmpty() && d.peekLast().value > x) d.pollLast();
            d.addLast(new pair(i, x));
            sb.append(d.peekFirst().value).append(" ");
        }
        System.out.println(sb);
    }
}