[백준] 11003 최솟값 찾기

📘 풀이한 문제

• 백준 11103 최솟값 찾기

---

⭐ 문제에서 주로 사용한 알고리즘

• 슬라이딩 윈도우

---

📜 대략적인 코드 설명

• 첫줄에 입력 숫자의 개수(N)와 인도우 크기(L)를 입력받습니다.
• 둘째 줄에 숫자를 입력받습니다.
• deque에는 숫자의 인덱스를 저장합니다.
• 반복문 (0~N)
• i번째 deque 마지막값이 입력숫자보다 큰 것을 모두 제거합니다.
• 제거가 끝나고, deque의 맨 앞숫자가 윈도우 안에 포함되는지 확인하고 벗어나면 지웁니다.
• 맨 앞 숫자를 정답 문자열에 추가합니다.

---

메모

컴퓨터네트워크 시간에 배운 적이 있는데, 다시는 보지말자는 마음으로 잊어버렸다. 그리고 이렇게 백준에서 만날줄 몰랐다. 다시 찾아서 정리해봐야겠다.

import java.io.*;
import java.util.*;

public class 최솟값_찾기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb=new StringBuilder();

        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int L = Integer.parseInt(input[1]);
        int[] numbers = new int[N];

        StringTokenizer numbersToken = new StringTokenizer(br.readLine(), " ");
        Deque<Integer> answerIndices = new LinkedList<>();

        for(int i=0; i<N; i++) {
            numbers[i] = Integer.parseInt(numbersToken.nextToken());
            while(!answerIndices.isEmpty() && numbers[answerIndices.getLast()] > numbers[i]) {
                answerIndices.removeLast();
            }
            answerIndices.addLast(i);
            if(!answerIndices.isEmpty() && answerIndices.getFirst() <= i-L) {
                answerIndices.removeFirst();
            }
            sb.append(numbers[answerIndices.getFirst()]).append(" ");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();

    }
}