[백준/JAVA] 11003번: 최솟값 찾기

🔺 문제

11003번: 최솟값 찾기

 

 

🔺 코드

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 = Integer.parseInt(st.nextToken());   // 데이터 개수
        int L = Integer.parseInt(st.nextToken());   // 최소값 구하는 범위 (= 슬라이딩 윈도우 크기)
        
        Deque<Node> myDeque = new LinkedList<>();
 
        st = new StringTokenizer(br.readLine()," ");
        for(int i = 0 ; i < N ; i++) {
            int now = Integer.parseInt(st.nextToken());
 
            // 덱 마지막 위치에서 now보다 큰 값은 덱에서 제거
            while(!myDeque.isEmpty() && myDeque.getLast().val > now) {
                myDeque.removeLast();
            }
            
            myDeque.addLast(new Node(now, i));  // 덱의 마지막 위치에 now값 저장
            
            // 범위에서 벗어난 값은 덱에서 제거 (범위 : i - L + 1 ~ i)
            if(myDeque.getFirst().idx <= i - L) {
                myDeque.removeFirst();
            }
            
            bw.write(myDeque.getFirst().val + " "); // 덱의 첫 번째 데이터(=최소값) 출력
        }
        
        bw.flush();
        bw.close();
    }
    
    // 덱에 저장할 노드 클래스
    static class Node {
        public int val;
        public int idx;
        
        Node(int val, int idx) {
            this.val = val;
            this.idx = idx;
        }
    }
}

✅ 해결 아이디어
✔ 슬라이딩 윈도우를 덱으로 구현
- 새로운 값 들어올 때마다 정렬 대신, 현재 수보다 큰 값을 덱에서 제거

 

 

---

🔺 다른 풀이들

- 최고의 풀이.. (복습용)

[BOJ] 백준 11003번 최솟값 찾기 (Java)

 

 

- Node 클래스를 만드는 대신 int 배열을 만들어 사용하셨다. 과정 설명도 짱

(JAVA) 백준 11003번 : 최솟값 찾기 --- [슬라이딩 윈도우]

 

---

💬 느낀 점

개념 자체는 어렵지 않은데..

직접 구현해보라면 아직은 못 할 것 같다..

복습혀야지,,,

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ Do it 알고리즘 코딩테스트 자바편