[백준] 11003번 풀이 (자바)

 문제 제시

 

Gold 1

 

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

 

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

예제 입력 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

 

 

 

 핵심 개념

• 투 포인터 (Two - Pointer)
• 슬라이딩 윈도우 (Sliding - Window)
• 덱/데크 (Deque)

 

 

 

 풀이

본격적으로 들어가기 전에 어떻게 코드를 구현해야 되는지 떠올려 봤을 때, 슬라이딩 윈도우로 이동하면서 매 순간마다 최솟값을 산출해내야 되므로 이중 반복문의 형태로 코드를 구현해야 된다는 것을 알 수 있다.

 

한 예로 L값이 3일 때 Ai-L+1 ~ Ai 식에 대입하면 Ai-2 ~ Ai 가 되므로 범위를 하나하나 나열하면 Ai-2, Ai-1, Ai 로 총 3개이다. L의 값을 늘려서 대입해도 범위의 개수는 L개로 동일하다. 즉 슬라이딩 윈도우에 들어갈 범위의 크기는 L인 것을 알 수 있다. L이 3이고 N이 5인 경우일 때 방금 설명한 것을 그림으로 표현하면 아래와 같다.

 

 

 

 

이 문제에서는 슬라이딩 윈도우에 들어온 수에서 최솟값을 구해야 하므로 잠시 슬라이딩 윈도우 값을 담을 임시 저장공간이 필요하다. 슬라이딩 윈도우 범위에 새로운 값을 넣음과 동시에 슬라이딩 윈도우 범위를 이탈하는 오래된 값은 빠져야 하므로 큐(Queue)의 형태로 코드를 구현해야 한다.

 

큐의 형태로 코드를 구현하려면 첫 번째 인덱스 값을 지워야 하는데, ArrayList에서 0번째 인덱스의 값을 지우면 자동적으로 그 뒤에 있는 값들을 복사해서 앞으로 붙여 넣으므로 성능상 안 좋다. 그래서 노드들로 연결된 링크드 리스트(Linked - List)로 큐를 구현했는데 그 코드는 아래와 같다.

 

 

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

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.valueOf(st.nextToken());
		int L = Integer.valueOf(st.nextToken());
		LinkedList<Integer> list = new LinkedList<>();
		int last = 0;
		
		st = new StringTokenizer(br.readLine());
		list.add(Integer.valueOf(st.nextToken()));   // list의 초기값 대입
		
		while (last < N) {
			int s = Collections.min(list);   // list에서 최솟값 추출
			sb.append(s).append(" ");
			if (last < L-1) {   // L의 길이만큼 리스트를 채우기
				last++;
				list.add(Integer.valueOf(st.nextToken()));
				continue;
			}
			if (last == N-1) {break;}   // 첫번째 인덱스 값을 지우고 뒤에 값을 추가
			list.remove(0);
			last++;
			list.add(Integer.valueOf(st.nextToken()));
		}
		bw.write(String.valueOf(sb).trim());
		bw.flush();
		br.close();
	}
}

 

 

그런데, 이 코드를 백준에 넣고 돌리면 시간 초과가 뜬다. 그래서 매 순간 최솟값을 구해야 되는 부분에 착안해서 우선순위 큐(PriorityQueue)로 다음과 같이 코드를 구현해 봤다.

 

 

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

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));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.valueOf(st.nextToken());
		int L = Integer.valueOf(st.nextToken());
		
		PriorityQueue<Node> deque = new PriorityQueue<>(); 
		st = new StringTokenizer(br.readLine());
		
		for (int i=0; i<N; i++) {
			int nextNum = Integer.valueOf(st.nextToken());   // 다음값 받기
			deque.offer(new Node(i, nextNum));   // 값 추가
			
			while (deque.peek().index <= i-L) {   // L의 범위에 벗어나는 오래된 값 제거
				deque.poll();
			}
			sb.append(deque.peek().value).append(" ");
		}
		bw.write(String.valueOf(sb));
		bw.flush();
		br.close();
	}
	
	static class Node implements Comparable<Node> {   // PriorityQueue의 내부적인 값 비교를 위한 Comparable 구현
		public int index;
		public int value;
		
		Node(int index, int value){
			this.index = index;
			this.value = value;
		}

		@Override
		public int compareTo(Node o) {
			return this.value - o.value;
		}
	}
}

 

 

역시나 이 코드 또한 시간 초과가 뜬다..ㅠㅠㅠ 이 때문에 한참을 고민하다가 결국 데크로 이 문제를 풀어야 된다는 것을 알게 됐다. 데크는 양방향으로 조작할 수 있는 자료구조인데, 내가 작성한 맨 위의 코드에서도 링크드 리스트를 이용해서 양방향으로 조작이 가능하게끔 만들었다.(새로운 값을 add로 추가, 오래된 값을 remove로 제거) 그런데도 백준에서 시간 초과가 뜨는 게 이상해서 구글링을 해봤더니, 자바만 안된다는 것 같더라..... 그래서 울면서 데크를 이용한 새로운 코드를 다음과 같이 작성해보았다.

 

 

 

 정답 코드

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

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));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.valueOf(st.nextToken());
		int L = Integer.valueOf(st.nextToken());
		
		Deque<Node> deque = new LinkedList<>(); 
		st = new StringTokenizer(br.readLine());
		
		for (int i=0; i<N; i++) {
			int nextNum = Integer.valueOf(st.nextToken());   // 다음값 받기
			
			while (deque.isEmpty()!=true && deque.peekLast().value>nextNum) {   // 새로 들어오는 값이 기존의 마지막 인덱스 값보다 큰지 작은지 비교해서 작으면 기존의 마지막 값 제거
				deque.pollLast();
			}
			deque.offerLast(new Node(i, nextNum));   // L의 범위에 벗어나는 오래된 값 제거
			if (deque.peekFirst().index <= i-L) {
				deque.pollFirst();
			}
			sb.append(deque.peekFirst().value).append(" ");
		}
		bw.write(String.valueOf(sb));
		bw.flush();
		br.close();
	}
	
	static class Node {
		public int index;
		public int value;
		
		Node(int index, int value){
			this.index = index;
			this.value = value;
		}
	}
}

 

 

 

 후기

자바를 사용한 일반적인 풀이법으로는 시간 초과 때문에 데크를 써야지만 풀 수 있는 문제이므로, 데크를 망각하고 있던 나와 같은 사람들에게는 여러 우여곡절이 있었을 것이다.(나처럼.....) 그래도 덕분에 데크에 관해서 깊이 알게 되는 기회가 되었으므로 나름 만족하며 글을 마친다.