백준 11003번 - 최솟값 찾기 Java(자바)

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

 

 

문제 설명

배열 인덱스 마다 자기자신과 ㅣ-1 전까지의 요소들중 가장 작은 값을 구하는 문제이다.

바킹독의 덱 문제집의 문제라 덱을 사용해야 한다는 생각으로 문제를 풀었다.

첫번째 줄에 숫자의 갯수와 l이주어지고

두번째 줄에 배열이 주어진다.

 

아이디어

덱과 조합하여 생각하니 직관적으로 스라이딩 윈도우가 생각이 났다.

1. 덱에서 제거
가장 먼저 생각한 것은 어떻게 나가는 가엿다.

for문으로 각 배열의 인덱스를 점검할때 현재 인덱스를 i 라고 한다면

i - l을 한다면 나가야 하는 인덱스 가 된다.

이때 배열 초반에는 i - l 을하면 마이너스가 되는데 이때에는 나가는 것이 없어야 하므로 if문으로 처리해 주었다.

 

2. 최솟값 추가

최솟값을 관리하기 위해서 덱에 넣을때 last에 넣게 되는데

문제에서 최솟값을 알아야하는 범위는 i인덱스의 이전 값들 중에서 이다. 따라서 덱에는 왼쪽에 해당 슬라이딩 윈도우에서 가장 최솟값이 있고 peekFirst()로 가져오면 되므로

peekLast로 넣기전에 확인해보며 현재 값이 작은 값이라면 removeLast를 하여 제거를 반복한뒤 넣어 주어 최솟값을 넣어주었다. 

 

1번과 2번을 합쳐 덱에는 현재 범위에서 최솟값만 남게 되니

peekFirst로 배열마다 순회하며 출력하였다.

 

이런 방식으로 값을 넣어가며 처리 할때 문제는 배열에 값이 중복되어 나온다는 것이다.

그래서 값도 비교하고 인덱스도 비교하기 위해 element라는 클래스를 만들어 수행하였다.

 

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
public class Main {
    public static void main(String[] args) throws IOException {
        class Element{
            int index;
            int value;
            public Element(int index, int value){
                this.index = index;
                this.value = value;
            }
        }
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int l = Integer.parseInt(st.nextToken());
        StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
        int[] arr = new int[n];
        int[] answer = new int[n];

        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st2.nextToken());
        }
        Deque<Element> deque = new LinkedList<>();
        deque.add(new Element(0, arr[0]));
        sb.append(deque.peekFirst().value).append(" ");
        //문자열 지나면서 정답 배열 만들기
        for(int i = 1; i < n; i++) {
            int out = i - l;
            //덱에 넣기
            //덱에 넣을때 삽입 정렬?
            //덱의 의미가 없어짐....

            //나가야 되는 인덱스면 나가게
            if( out >= 0 && deque.peekFirst().index == out ){
                deque.removeFirst();
            }

            //최솟값이 나오도록 최솟값 저장
            while(!deque.isEmpty()){
                if(deque.peekLast().value > arr[i]){
                    deque.removeLast();
                }else{
                    break;
                }
            }

            deque.addLast(new Element(i, arr[i]));
            sb.append(deque.peekFirst().value).append(" ");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

}