BOJ 11003 최솟값 찾기 by Java

ejjem·2025년 8월 14일

목록 보기

15/20

문제 풀이 날짜: 2025-08-13

💡Github URL

https://github.com/ejjem/coding-test/tree/main/%EB%B0%B1%EC%A4%80/Platinum/11003.%E2%80%85%EC%B5%9C%EC%86%9F%EA%B0%92%E2%80%85%EC%B0%BE%EA%B8%B0

💡 초기 접근

일정 범위 안에서 최솟값을 구하는 문제이기 때문에 슬라이딩 윈도우를 사용해야겠다고 생각했음.
그러나 주어진 값의 범위가 최대 5,000,000이기 때문에 매번 윈도우를 정렬하여 윈도우 내 최솟값을 찾는 것은 불가능 ( 정렬은 O(NlogN) )
때문에 O(N)의 방식을 목표로 풀이를 진행해야 함. 이에 뭔가 다른 방법이 필요하다고 생각했지만, 스스로 풀어내지는 못했음.
단조 덱(Monotonic Deque)를 사용하면 풀이가 가능하다고 함.

cf) 단조 덱

단조(Monotonic)

데이터가 항상 증가하거나 감소하는 특징
ex) 1, 2, 3, ... n -> 단조 증가

단조 덱의 핵심 원리

1. 단조성 유지
덱에 데이터를 삽입할 때, 현재 덱의 맨 마지막 요소와 비교하여 현재 요소가 더 크거나 같으면(단조 증가) 마지막 요소를 제거하고 현재 요소를 추가. 이렇게 하면 덱의 요소들이 항상 단조 증가하는 순서로 유지됨.
2. 최적의 값 유지
덱의 맨 앞에는 현재 윈도우에서 가장 큰 값(또는 작은 값)이 항상 위치하게 됨. 덱의 맨 앞 요소를 제거하거나 새로운 요소를 추가할 때, 덱의 단조성을 유지하면서 최적의 값을 유지.

💡알고리즘 설계

윈도우로 deque 자료구조를 사용. deque에 들어가는 노드는 (index, value) 형태.
새로운 노드를 넣을 때 마다 단조 특성을 유지하기 위해, 새로운 노드 기준으로 윈도우 내에는 새로운 노드보다 작은 값만 유지하고 나머지는 전부 pop(deque니까 pollLast)해서 제거해야 함. 이렇게 하면 윈도우 내부는 단조 증가 형태가 유지되고 맨 앞 노드가 최솟값, 맨 뒤 노드가 최댓값으로 항상 보장됨.
따라서 윈도우 내 값들이 인덱스에 맞춰서 윈도우 내에 유지될 수 있는 상태라면, 문제에서 찾아야 하는 최솟값은 윈도우 내 가장 앞쪽 노드가 됨.

💡코드

메모리: 640944 KB, 시간: 2000 ms

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

class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static StringBuilder sb;
    static int N, L;
    
    public static void main(String[] args) throws Exception{
    	br = new BufferedReader(new InputStreamReader(System.in));
    	st = new StringTokenizer(br.readLine());
    	sb = new StringBuilder();
    	N = Integer.parseInt(st.nextToken());
    	L = Integer.parseInt(st.nextToken());
    	ArrayDeque<int[]> window = new ArrayDeque<>();
    	int size = 1;
    	st = new StringTokenizer(br.readLine());
    	
    	// {index, value}
    	window.offerLast(new int[] {0, Integer.parseInt(st.nextToken())});
    	sb.append(window.peekFirst()[1]).append(" ");
    	for(int i=1; i<N; i++) {
    		int tmp = Integer.parseInt(st.nextToken());
    		
    		// window에 삽입
    		// 1. 최솟값 정렬
    		while(true) {
    			if(!window.isEmpty() && window.peekLast()[1] >= tmp) {
    				window.pollLast();
    				size --;
    			}else {
    				window.offerLast(new int[] {i, tmp});
    				size ++;
    				break;
    			}
    		}
    		// 2. 사이즈 확인
    		while(size > L || (i - window.peekFirst()[0]) >= L) {
    			window.pollFirst();
    			size --;
    		}
    		/*
    		System.out.println("--------");
    		System.out.println(i + "번째");
    		for (int[] e : window) {
    		    System.out.println(Arrays.toString(e));
    		}
    		*/
    		
    		// 최솟값 출력
        	sb.append(window.peekFirst()[1]).append(" ");
    	}
    	bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	bw.write(sb.toString());
    	bw.flush();
    	bw.close();
    }
}