[JAVA] 0x07 백준 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를 공백으로 구분하여 순서대로 출력한다.

예제 입력 1

12 3
1 5 2 3 6 2 3 7 3 5 2 6

예제 출력 1

1 1 1 2 2 2 2 2 3 3 2 2

🔑 키워드.

특정 구간에서의 최솟값을 구해야 한다. . . → 슬라이딩 윈도우? , 우선 순위 큐?

문제 풀이

[(A-L+1) ~ A] 길이 L의 구간에서 최솟값을 계속 트래킹하면서 구해야한다. 첫 이문제를 맞닥뜨렸을 때 슬라이딩 윈도우가 생각났으며 해당 구간의 최솟값을 지역변수로 선언하여 더 작은 값이 들어오면 최솟값을 최신화하는 방법을 생각했다.

예시 ) 

 1   5   2   3   6   2   3   7   3   5   2   6
[1]
최솟값 : 1

 1   5   2   3   6   2   3   7   3   5   2   6
[1   5]
최솟값 : 1

 1   5   2   3   6   2   3   7   3   5   2   6
[1   5   2]
최솟값 : 1

 1   5   2   3   6   2   3   7   3   5   2   6
     [5   2   3]
최솟값 : ?

위 예시와 같이 기존 최솟값 1이 구간 L에 벗어나게 되었을 때, 그 다음 최솟값 2를 알 수 있는 방법이 없었다.
즉 다시 생각해 보았다.

이전에 stack관련 문제를 풀었을 때 특정 값보다 작거나 클 때 까지 pop을 하며 필요없는 값을 버렸던 기억이 났다.

예시 ) 

 1   5   2   3   6   2   3   7   3   5   2   6
[1]
최솟값 : 1

 1   5   2   3   6   2   3   7   3   5   2   6
[1   5]  #일단은 필요한 값. 뒤에 어떤 값이 나올 지 모르기 때문
최솟값 : 1

 1   5   2   3   6   2   3   7   3   5   2   6
[1        2] # 5는 2가 들어옴으로써 더이상 필요가 없으므로 pop 후 2를 집어넣음.
최솟값 : 1

 1   5   2   3   6   2   3   7   3   5   2   6
         [2   3]
최솟값 : 2

최솟값은 deque의 왼쪽 부분에 남겨놓고 최솟값이 될 수 있는 후보군은 오른쪽에 두었다. Index도 함께 저장해야 해당 최솟값이 구간 L에서 벗어났을 때 deque.pollFirst()를 사용해 최솟값을 최신화 할 수 있었다.

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));
        String[] line = br.readLine().split(" ");
        int N = Integer.parseInt(line[0]);
        int L = Integer.parseInt(line[1]);
        Deque<Integer> deque = new ArrayDeque<>();
        Deque<Integer> deque2 = new ArrayDeque<>();
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i =0; i<N; i++){
            int num = Integer.parseInt(st.nextToken());
            if(!deque2.isEmpty()&&i-deque2.peekFirst() >= L){//최솟값이 구간 L에서 벗어났을 때 왼쪽으로 뺀다.
                deque.pollFirst();
                deque2.pollFirst();
            }
            while(!deque.isEmpty() && deque.peekLast()>=num)
            {
                deque.pollLast();
                deque2.pollLast();
            }
            deque.addLast(num);
            deque2.addLast(i);
            sb.append(deque.peekFirst()).append(" ");

        }
        System.out.println(sb.toString().trim());
        br.close();
    }
}

최솟값 ⇒ 우선순위 큐를 활용할 수도 있지 않을까? 해서 도전해보았따 .. 시간초과가 나버렸다.

package week6;
//최소값 찾기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class boj11003_2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int N = Integer.parseInt(line[0]);
        int L = Integer.parseInt(line[1]);
        PriorityQueue<int []> pq=new PriorityQueue<>((o1, o2) -> {
            if (o1[0]==o2[0]) return o1[1]-o2[1];
            return o1[0]-o2[0];
        });
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i =0; i<N; i++){
            int num = Integer.parseInt(st.nextToken());
            while(!pq.isEmpty()&&i - pq.peek()[1] >= L){//구간에 만족하는 최솟값이 나올때까지 빼기
                pq.poll();
            }
            pq.add(new int[]{num, i});
            sb.append(pq.peek()[0]).append(" ");

        }
        System.out.println(sb.toString().trim());
        br.close();
    }
}

결론

Deque는 기본적으로 맨 앞이 최솟값을 유지할 수 있도록 도와주는 자료구조이다. 특히 특정 구간의 최솟값을 구할 때 자주 쓰이는 자료구조라고 한다. 이를 기억하길..