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

#11003 최솟값 찾기

난이도 : 플레 5

유형 : 슬라이딩 윈도우 / Deque

11003번: 최솟값 찾기

▸ 문제

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를 공백으로 구분하여 순서대로 출력한다.

 

문제 풀이  

슬라이딩 윈도우 알고리즘을 사용하여 풀이를 하는 문제이다.

 

📚 조건

• 배열 크기 N, 구간 크기 L( 1 <= L <= N <= 5,000,000)
• 배열 원소 Ai ( -109 <= Ai <= 109)

모든 원소를 비교하면 시간복잡도 O(N^2)로 시간초과가 발생한다.

 

구간의 고정 길이를(즉 창문의 너비를) L은 한 칸이라도 옆으로 움직이면 L-1 칸은 겹치게 된다.

• 기존 모습 : ⬜️🟦🟦🟦🟦⬜️⬜️
• 다음 모습 : ⬜️⬜️🟦🟦🟦🟦⬜️

기존 구간과 새 구간의 ⬜️🟦🟪🟪🟪🟦⬜️ 보라색 부분은 겹치게 된다. 보라색 부분은 새 구간에도 포함이 되어 있으므로 새 구간에서는 빠지게 된 앞의 🟦 와 새 구간에 포함되게 된 🟦 만 비교하게 되면 더 효율적일 것이다. 시간 복잡도 O(N^2)을 피하고 O(N)으로 풀이할 수 있다.

 

탐색 과정

양방향 Queue인 Deque를 사용했다. Deque의 데이터 타입은 int[] 배열로 첫 번째 인자에는 데이터를 넣어주고 두 번째에는 인덱스를 넣어주었다. { num , idx }

 

i=0 : [ {1,0} ]   ☛ bw.write : 1

i=1 : [ {1,0}, {5,1} ] ☛ bw.write : 1 1

i=2 : [ {1,0}, {5,1}, {2,2} ] ☛ bw.write : 1 1 1

→ 새로 들어오는 값보다 이전의 값이 더 크다면 값을 빼준다. (5>2 :  q.peekLast()[0] > num)

 

i=3 : [ {1,0}, {2,2}, {3,3} ] ☛ bw.write : 1 1 1 2

→ 현재 최솟값의 인덱스가 창문의 너비 값을 벗어나면 삭제해준다. (0 < 1 : q.peek()[1] < i -(l-1))

 

i=4 : [ {2,2}, {3,3}, {6,4} ] ☛ bw.write : 1 1 1 2 2

i=5 : [ {2,2}, {3,3}, {6,4}, {2,5} ] ☛ bw.write : 1 1 1 2 2 2

→ 새로 들어오는 값보다 이전의 값이 더 크다면 값을 빼준다. (3,6 > 2 : q.peekLast()[0] > num)

→ 현재 최솟값의 인덱스가 창문의 너비 값을 벗어나면 삭제해준다. (2 < 3 : q.peek()[1] < i -(l-1))

 

i=6 : [ {2,5}, {3,6} ] ☛ bw.write : 1 1 1 2 2 2 2

i=7 : [ {2,5}, {3,6}, {7,7} ] ☛ bw.write : 1 1 1 2 2 2 2 2

i=8 : [ {2,5}, {3,6}, {7,7}, {3,8} ] ☛ bw.write : 1 1 1 2 2 2 2 2 3

→ 새로 들어오는 값보다 이전의 값이 더 크다면 값을 빼준다. (7 > 3 : q.peekLast()[0] > num)

→ 현재 최솟값의 인덱스가 창문의 너비 값을 벗어나면 삭제해준다. (5 < 6 : q.peek()[1] < i -(l-1))

 

i=9 : [ {3,6}, {3,8}, {5,9} ]  ☛ bw.write : 1 1 1 2 2 2 2 2 3 3

i=10 : [ {3,6}, {3,8}, {5,9}, {2,10} ]  ☛ bw.write : 1 1 1 2 2 2 2 2 3 3 2

→ 새로 들어오는 값보다 이전의 값이 더 크다면 값을 빼준다. (3,5 > 2 : q.peekLast()[0] > num)

 

i=11 : [ {2,10}, {3,11} ]  ☛ bw.write : 1 1 1 2 2 2 2 2 3 3 2 2

 

풀이 코드 

양방향 큐인 Deque를 사용하여 풀이하였다. 우선순위 큐를 사용해도 되지만 Java로는 해당 문제의 시간 제한에 통과하기가 어렵다.

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

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<int[]> q = new ArrayDeque<>();
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			int num = Integer.parseInt(st.nextToken());
			while(!q.isEmpty() && q.peekLast()[0] > num) q.pollLast();
			
			q.offer(new int[] {num,i});
			if(q.peek()[1] < i -(l-1)) {
				q.poll();
			}
			bw.write(q.peek()[0]+" ");
		}
		bw.flush();
		bw.close();
	}
}

 

우선순위 큐 풀이 (Java 시간초과)

PriorityQueue풀이는 시간초과를 당한다. 다른 언어는 잘 통과한다던데 Java만 이렇다...

 

Deque와의 차이는 데이터 정렬 여부와 값 데이터 삭제 과정이다.

 

Deque는 정렬을 하지 않고 새로운 값이 안에 들어있는 값보다 크면 while문을 통해 바로 삭제해주고 그 구간에 속하는 최솟값을 출력해준다. PriorityQueue는 값을 기준으로 데이터를 정렬해준다. 그 다음 최솟값이 구간에 속하는지 확인하고 출력해준다.

 

두 로직의 가장 큰 차이는 정렬의 여부이다.

데이터 삭제 로직의 틀은 똑같은 데 정렬의 여부에 따라 우선순위 큐에서 생략됐을 뿐이다. 그러므로 PriorityQueue 데이터 정렬 과정에서 시간을 잡아먹어서 시간초과가 발생함을 추론해 볼 수 있다.

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

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());
		StringBuilder sb = new StringBuilder();
		
		int n = Integer.parseInt(st.nextToken());
		int l = Integer.parseInt(st.nextToken());
		
		// 우선순위 큐 풀이는 시간초과!!
		Queue<int[]> q = new PriorityQueue<>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0] - o2[0];
			}
		});
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			int num = Integer.parseInt(st.nextToken());
			q.offer(new int[]{num,i});
			while((q.peek()[1] < i - (l-1))) {
				q.poll();
			}
			bw.write(q.peek()[0]+" ");
		}
		bw.flush();
		bw.close();
	}
}