[알고리즘 코테 #7] 최솟값 찾기

도경원

Sep 04, 2025

Contents

문제 입력 출력 예제 입력 1 예제 출력 1 코드 회고

문제

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

코드


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());
		st = new StringTokenizer(br.readLine());
		Deque<Node> mydeque = new LinkedList<>();
		for(int i=0; i<N; i++) {
			int now = Integer.parseInt(st.nextToken());
			// 새로운 값이 들어올 때마다 정렬 대신 현재 수보다 큰 값을 덱에서 제거해 시간 복잡도를 줄인다.
			while(!mydeque.isEmpty() && mydeque.getLast().value > now) {
				mydeque.removeLast();
			}
			mydeque.addLast(new Node(now, i));
			// 범위에서 벗어난 값은 덱에서 제거
			if(mydeque.getFirst().index <= i-L) {
				mydeque.removeFirst();
			}
			bw.write(mydeque.getFirst().value + " ");
		}
		bw.flush();
		bw.close(); 
	}
	
	static class Node {
		public int value;
		public int index;
		
		Node(int value, int index) {
			this.value = value;
			this.index = index;
		}
	}
}

회고

❗

슬라이딩 윈도우 기법과 덱을 사용해서 문제를 풀었다. 비슷한 문제가 나왔을때 문제 없이 풀수 있도록 잦은 연습이 필요할 것 같다

Contents

문제 입력 출력 예제 입력 1 예제 출력 1 코드 회고

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()); st = new StringTokenizer(br.readLine()); Deque<Node> mydeque = new LinkedList<>(); for(int i=0; i<N; i++) { int now = Integer.parseInt(st.nextToken()); // 새로운 값이 들어올 때마다 정렬 대신 현재 수보다 큰 값을 덱에서 제거해 시간 복잡도를 줄인다. while(!mydeque.isEmpty() && mydeque.getLast().value > now) { mydeque.removeLast(); } mydeque.addLast(new Node(now, i)); // 범위에서 벗어난 값은 덱에서 제거 if(mydeque.getFirst().index <= i-L) { mydeque.removeFirst(); } bw.write(mydeque.getFirst().value + " "); } bw.flush(); bw.close(); } static class Node { public int value; public int index; Node(int value, int index) { this.value = value; this.index = index; } } }