[백준/JAVA] 11003 최솟값찾기

https://www.acmicpc.net/problem/11003

11003번: 최솟값 찾기

문제분류

자료구조, 우선순위큐, 덱

 

문제분석

정해진 구간 L에 대하여 최솟값을 구하는 문제

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
	static class Pair{
		int x,y;
		public Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int n,l;
	static Deque<Pair> dq = new ArrayDeque<>();

	static void est() throws IOException {st = new StringTokenizer(br.readLine());}
	static int rstn() {return Integer.parseInt(st.nextToken());}

	public static void main(String[] args) throws IOException {
		est(); n=rstn(); l =rstn(); est();
		for(int i=0; i<n; ++i){
			int num = rstn();
			while(!dq.isEmpty()&&dq.peekLast().x>num) dq.pollLast();
			while(!dq.isEmpty()&&dq.peekFirst().y<=i-l) dq.pollFirst();
			dq.add(new Pair(num,i));
			sb.append(dq.peekFirst().x).append(" ");
		}
		System.out.println(sb.toString());
	}
}

 

문제풀이

해당 문제는 일정한 구간에 대한 최소값을 구하는 문제이다. 
슬라이딩 윈도우로 구간에대한 최소값을 구하기 위하여 deque를 사용하였다. 
deque의 가장 앞부분에 최소값을 설정해놓고 윈도우를 이동시켜가면 된다.

dq를 사용한 이유는 양쪽에서의 접근이 필요하기 때문이다. 첫째로 앞부분에 대한 접근은 최소값을 구해내기 위해서, 윈도우가 지나갔을 때 원소를 빼내기 위해서 사용한다. 윈도우가 지나갔을때를 판단하기 위해 Pair클래스로 인덱스를 같이 저장해준다.

그리고 뒷쪽은 윈도우 범위에 들어갔을때 원소를 넣어주기 위함인데, 들어가는 원소를 a 윈도우 안에있는 원소들을 b1,b2....라고 한다면 

a보다 큰 bi들은 a가 들어가는 순간 절대 최소값이 될 수 없다. 적어도 a가 윈도우에 들어오는 순간부터 bi가 윈도우 바깥으로 나갈때까지 a가 윈도우 안에 존재하기 때문이다. 그렇기때문에 a를 dq에 밀어넣을 때 a보다 작은 값이 last에 위치할 때 까지 원소를 poll해준다.

그렇게되면 항상 dq의 first위치에는 구간의 최소값이 존재하게된다.

처음에는 priorityQueue로 구현했었다. 이유는 minHeap으로 구현하면 deque에서의 원소를 넣을 때 pop하는 과정 없이 최소원소가 윈도우를 벗어났는지 아닌지만 판단하면 되기 때문에 구현이 좀 더 짧았기 때문이다. 

시간복잡도도 nlogn으로 1억이 조금 넘는다. 그렇기에 사실 간당간당하게 통과할 줄 알았지만, 자바의 한계였다. 

결국 nlogn의 풀이를 포기하고 deque를 사용하여 구현하였다.

(c++기준으로 pq의 풀이도 통과한다고 한다.)