[Boj_11003] 최솟값 찾기

📎 문제 링크

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

 

▸ 문제

N개의 수 A1, A2, ..., AN과 L이 주어진다.

Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오.

이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

 

▸ 입력

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

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

 

▸ 출력

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

 

📍 문제 정보

• 💍 문제 레벨 : 플레티넘 5
• 🔔  문제 유형 : 자료구조, 우선순위 큐, 덱
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

슬라이딩 윈도우 알고리즘을 사용해서 풀 수 있는 문제이다.

구간의 고정 길이 l만큼 슬라이딩을 움직이며 최솟값을 구해주면 된다.

 

Java에서 우선순위 큐 풀이는 시간초과로 통과하지 못한다고 하여

양방향 Queue인 Deque를 사용했다.

Deque의 데이터 타입은 int[] 배열로 첫 번째 인자에는 입력받은 데이터를 넣어주고, 

두 번째 인자에는 인덱스를 넣어주었다. ➡ {num, idx}

 

문제의 예제 입력 1을 예시로 들어보면,

 

i = 0 : [ {1, 0} ] ➡ 1

i = 1 : [ {1, 0}, {5, 1} ] ➡ 1, 1

i = 2 : [ {1, 0}, {5, 1}, {2, 2} ] ➡ 1, 1, 1

➡ 새로 들어오는 값보다  이전의 값이 크다면 제거한다. (5 > 2 : deque.peekLast()[0] > num) 

 

i = 3 :  [ {1, 0}, {2, 2}, {3, 3} ] ➡ 1, 1, 1, 2

➡ 현재 최솟값의 인덱스가 구간의 고정 길이를 벗어나면 제거한다. (0 < 1 : deque.peek()[1] < i - (l-1))

 

i = 4 :  [ {2, 2}, {3, 3}, {6, 4} ] ➡ 1, 1, 1, 2, 2

i = 5 :  [ {2, 2}, {3, 3}, {6, 4}, {2, 5} ] ➡ 1, 1, 1, 2, 2, 2

➡ 새로 들어오는 값보다 이전의 값이 크다면 제거한다. (3, 6 > 2)

➡ 현재 최솟값의 인덱스가 구간의 고정 길이를 벗어나면 제거한다. (2 < 3)

 

i = 6 : [ {2, 5}, {3, 6} ] ➡ 1, 1, 1, 2, 2, 2, 2

i = 7 : [ {2, 5}, {3, 6}, {7, 7} ] ➡ 1, 1, 1, 2, 2, 2, 2, 2

i = 8 : [ {2, 5}, {3, 6}, {7, 7}, {3, 8} ] ➡ 1, 1, 1, 2, 2, 2, 2, 2, 3

➡ 새로 들어오는 값보다 이전의 값이 크다면 제거한다. (7 > 3)

➡ 현재 최솟값의 인덱스가 구간의 고정 길이를 벗어나면 제거한다. (5 < 6)

 

i = 9 : [ {3, 6}, {3, 8}, {5, 9} ] ➡ 1, 1, 1, 2, 2, 2, 2, 2, 3, 3

i = 10 : [ {3, 6}, {3, 8}, {5, 9}, {2, 10} ] ➡ 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 2

➡  새로 들어오는 값보다 이전의 값이 크다면 제거한다. (3, 5 > 2)

 

i = 11 : [ {2, 10}, {6, 11} ] ➡ 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 2

 

위 풀이대로 코드를 작성해 보면 아래와 같다.

 

✔ 최종 코드

메모리 : 962996KB
시간 : 2312ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int l = Integer.parseInt(st.nextToken()); // 고정구간

        StringBuilder sb = new StringBuilder();
        Deque<int[]> deque = new ArrayDeque<>(); // num, idx
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(st.nextToken());
            while (!deque.isEmpty() && deque.peekLast()[0] > num) {
                deque.removeLast();
            }
            deque.offer(new int[] {num, i});
            if (deque.peek()[1] < i - (l-1)) {
                deque.remove();
            }
            sb.append(deque.peek()[0]).append(" ");
        }

        System.out.println(sb.toString());
    }
}

 

해결 완료 ! 🔥