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

참고로 동일한 코드에서 한번은 시간초과, 한번은 성공의 결과가 나왔다.(백준)
알아본결과 이 문제는 이슈가있는것같다.

문제 분석

N의 최대값이 5,000,000이고 시간 제한이 2.4초 이므로 시간복잡도 O(n)안에 해결해야한다.
일정 범위 안에서 최솟값을 구하는 문제이므로, 정렬과 슬라이딩 윈도우를 사용하면 될 것 같다.
하지만 정렬은 nlog(n)의 시간복잡도를 가지므로, 정렬을 사용할 수 없다.
하지만 슬라이딩 윈도우를 덱으로 구현하여 정렬 효과를 볼 수 있다!

슈도코드

N L 입력받기
for(N만큼 반복) {
	Ai 숫자 입력받아 배열 A에 저장
}
Deque<Node> checkDeque정의

for(i : 0~N-1 반복) {
	now(현재 데이터 값)
    덱 마지막위치에서부터 now보다 큰 값은 덱에서 제거
    덱 마지막 위치에 now값 저장
    덱 처음부터 L의 범위 벗어난 값(now index - L >= index) 덱에서 제거
    덱의 첫번째 데이터 출력
}

노드 클래스 생성 {
	index
    value
}

제출코드

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

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;
		}
	}
}

공부한 사항

• 자료구조 : Deque
• BufferedWriter 사용법
• 생성한 class의 사용법