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

백준 11003번 문제  -  최솟값 찾기

11003번: 최솟값 찾기

---

 

문제 분석

 

 

• N개의 수를 입력받고, N개의 각 인덱스(i)마다 i-L부터 i까지의 수 중 최솟값을 구하는 문제

 

---

해결 키 포인트

• 시간이 2.4초 밖에 없다
• 출력과 입력에서도 최소한의 시간만을 써야 함 (BufferedReader / BufferedWriter)
• 덱(Deque) 이용해 값을 정렬하는 시간을 줄이기
• Node 클래스(index, value)를 제작해 덱을 활용

 

---

덱(Deque) 설명

 

덱의 구조는 다음과 같다. 즉 덱의 특징은 "양 끝으로 데이터 삽입 삭제가 가능" 이다

Do It! 알고리즘 코딩 테스트 기본

 

덱 활용 방법

• 덱 맨 뒤에 존재하는 data의 value가 현재 삽입하는 data의 value 보다 작은 data는 다 삭제
• 덱에 data를 삽입
• 덱 맨 앞에 존재하는 data의 index가 현재 index - L(최솟값 구간) 보다 작은 data는 다 삭제

 

이렇게 하여 덱에 data를 삽입하는 동시에 정렬한다.

---

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.Deque;
import java.util.LinkedList;

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));
		
		// 입력 개수 N과 구간 수 L 입력
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int L = Integer.parseInt(st.nextToken());
		
		// N개의 수 입력
		st = new StringTokenizer(br.readLine());

		// 값을 보관 및 정렬 해 줄 deque
		Deque<Node> mydeque = new LinkedList<>();
		
		for(int i=0;i<N;i++) {
			int now = Integer.parseInt(st.nextToken());

			// 덱이 비거나, 덱 마지막에 현재 값(now)보다 큰 값 지우기
			while(!mydeque.isEmpty() && mydeque.getLast().value > now) 
				mydeque.removeLast();
			
			// 덱 마지막에 값 삽입
			mydeque.addLast(new Node(i, now));
				
			// 덱의 첫번째 인덱스에서 범위를 벗어난 값 지우기
			while(mydeque.getFirst().index <= i-L)
				mydeque.removeFirst();
			
          		  // 최소값 출력
			bw.write(mydeque.getFirst().value +" ");
		}
		bw.flush();
	}
}

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