[백준 알고리즘] 11003번 자바(Java) 최솟값 찾기

조건

 

문제

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

 

풀이

처음에는 힙을 생각했었다. 최솟값을 O(log N)만에 찾을 수 있기때문이다.

그래서 이제 힙에 값을 넣고 추후에 i-L 위치가 되면 그 값을 찾아내서 힙에서 제외시킬려고 했다.

문제는 여기서 발생한다. 힙의 최솟값 접근은 O(log N)이지만 특정 값 찾는 시간복잡도는 

무려  O(Nlog N)이다. 

 

따라서 힙으로 푸는 방법은 포기하고 다른 방식을 생각해봤다.

i-l부터 i까지들어가있는 덱이 있는데 

이제 새로 값이 들어왔을때 덱의 마지막값부터 시작해서 비교를 해나가는거다. 

만일 마지막값보다 새로들어온 값이 더 작으면 

마지막값은 poll()시켜준다. 그렇게되면 deque마지막값에는 제일 큰 값이 남아있고

맨 첫값에는 제일 작은 값이 남아있다.

이것을 활용하면 다음 그림과 같다.

빨간 화살표를 통해 어느값을 입력받는지 표현

 

5값 들어올때 과정

부가 설명으로는 5가 1보다 크다 따라서 없어지지 않고 들어온다

 

2값 들어올때 과정

 

3값 들어올때 과정

 

이런식으로 반복하게 된다. 이를 토대로 짠 코드는 아래와 같다.

 

 

 

예제 입력 예시

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

 

예제 출력 예시

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

 

소스코드

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

//11003번 최솟값 찾기

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());

        Deque<int[]> deque = new ArrayDeque<>();  //0에는 num의 값, 1에는 num의 index값

        st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(st.nextToken());
            while(!deque.isEmpty()&&deque.peekLast()[0]>num){
                deque.pollLast();
            }
            deque.add(new int[]{num, i});  //값과 위치 대입
            if(deque.peekFirst()[1] == i-l) deque.pollFirst();

            //이제 deque에는 가장 작은값이 맨앞이고 그 값이 곧 최솟값인 D이다
            int d = deque.peekFirst()[0];
            sb.append(d+" ");
        }
        System.out.println(sb);
    }
}

 

 

 

 

문제 출처

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

11003번: 최솟값 찾기