[JAVA][Baekjoon] 11003번 최솟값 찾기 ⭐️⭐️⭐️⭐️

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

---

 

🚫 시간초과 코드

처음에 너무 단순하게 그냥 반복문으로 구간마다 최솟값을 찾아서 출력하려 했었다....

완전 멍청이 코드였다 😡💢

 

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

public class Main {
   public static void main(String [] args) throws IOException{

       int N, L;
       Scanner sc = new Scanner(System.in);

       N = sc.nextInt();
       L = sc.nextInt();

       int [] arr = new int[N];

       for(int i=0; i<N; i++){
           arr[i] = sc.nextInt();
       }

       for(int i=0; i<N; i++){
           long min = 1000000000;
           if(i-L+1 < 0){
               for(int j=0; j<=i; j++){
                   if(min>arr[j]){
                        min = arr[j];
                    }
               }
           }
           else{
               for(int j=i-L+1; j<=i; j++){
                   if(min>arr[j]){
                       min = arr[j];
                   }
               }
           }
           System.out.print(min + " ");
       }
   }
}

 

📌 접근 방법 

일정 범위 안에서 최솟값을 구하는 문제는 슬라이딩 윈도우와 정렬을 사용하는 것 추천!

➡️ Deque(덱) 사용 !! (슬라이딩 윈도우를 deque로 표현하여 정렬 효과 )

 

🥐 Deque 란?

양방향으로 값을 삽입 및 삭제할 수 있는 자료구조

 

<Reference>

[JAVA] Deque 덱 이란?

 

 

• Deque에 value, index 값을 저장하여 비교
• 반복문을 통해 새로 삽입하는 값이 더 작으면 앞의 요소들을 제거하는 식으로 구현한다.

 

✅ pass code

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

public class Main {
   public static void main(String [] args) throws IOException{
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       StringTokenizer st = new StringTokenizer(br.readLine());

       int N, L;
       N = Integer.parseInt(st.nextToken());
       L = Integer.parseInt(st.nextToken());

       st = new StringTokenizer(br.readLine());

       Deque<Node> deque = new LinkedList<>();

       for(int i = 0; i < N; i++) {
           int num = Integer.parseInt(st.nextToken());

           while(!deque.isEmpty() && deque.getLast().value > num){
               deque.removeLast();
           }
           deque.addLast(new Node(num, i));

           if(deque.getFirst().index <= i - L) {
               deque.removeFirst();
           }
           bw.write(deque.getFirst().value + " ");
       }
       bw.flush();
       bw.close();

   }
   static class Node {
       public int index;
       public int value;

       Node(int value, int index) {
           this.value = value;
           this.index = index;
       }
   }
}

 

 

---

Reference

[Java / 자료구조] Deque 개념 및 정리