010. 최소값 찾기(백준11003번)

문제

문제 분석하기

처음 문제를 읽었을때, 잘 이해가 되질 않았다.
천천히 정리하며 기록해보자

예제를 기준으로 설명해보겠다.

$N=12$ , $L=3$
$A_N == A_{12}$

$A_{i-L+1}$ ~ $A_i$ 중 최소값이 $D_i$ 일 때, D에 저장된 수를 출력해야한다. $i <= 0$ 은 무시한다.

둘째 줄에는 N개의 수 $A_i$ 가 주어진다. $(-10^9 <= A_i <= 10^9)$
-> 즉, $i <= 0$ 을 무시한다는 지문에 따라 무시하면
-> $0< i <= N === 0< i <= 12$ 가 된다.
-> $A_{12-3+1}$ ~ $A_{12}$ 중 최소값 = 3을 윈도우로 잡고 윈도우 안 최소값을 구하는 문제이다.

$i$ 는 1부터 시작한다.

$A_1, A_2, ..., A_{12}$
1, 5, ..., 6 이 되는 것이다.

결론적으로,
$A_{1-3+1}$ ~ $A_{1}$ 중 최소값, $A_{2-3+1}$ ~ $A_{2}$ 중 최소값, ...., $A_{12-3+1}$ ~ $A_{12}$ 중 최소값 을 출력하면 될 것같다.

,

...

,

자, 지문 자체는 조금 이해가 된 것 같다.
추가로 문제를 분석해 얻을 수 있는 정보를 이용해 어떻게 접근할 것인지 생각해보자

JAVA11 기준 시간제한은 2.6초 이다.
-> 약 2억 6천만의 연산안에 결과가 도출되어야 한다.

제공된 $N$ 의 데이터는 $1 <= N <= 5,000,000$ 이다.
위 이미지 안 윈도우 안에서 정렬 후 최소값을 출력한다면, 시간복잡도는 $O(nlogn)$ 이 되어버려서 시간을 초과하게 된다. 그럼 어떻게 해야할까?

손으로 풀어보기

바로 덱을 사용해 접근하는 것이다.

덱에 들어갈 노드를 클래스로 구현해 저장한다. (index, value)

class Node {
	int index;
	int value;
}

(1, 1), (2, 5), ..., (12, 6) 이런 식으로 저장이 될텐데, 덱의 크기는 3 그리고 최소값만을 남겨 출력해야한다.

(1, 1), (2, 5), (3, 2) 중 마지막 (3, 2) 가 저장될때 덱의 마지막 요소와 비교후 큰수를 제거시킨다.
덱의 마지막 요소인 (2, 5)와 비교 후 (2, 5) 노드는 제거되고 남아있는 덱의 마지막 요소인 (1, 1) 와 비교해 큰수가 아니므로 멈춘다.

윈도우의 크기를 유지시키기 위해
(3, 2) 가 저장될 때 덱의 첫번째 요소의 인덱스 와 비교한다.
3(마지막 인덱스) - 3(윈도우 크기) < 1 이 조건을 충족하므로 저장
만약, 다음요소인 (4, 3) 이 들어오면 4 - 3 < 1 이 조건을 만족하지 않으므로, 첫번째 요소를 삭제시켜줘야 한다.

슈도코드 작성하기

N(데이터 개수), L(최소값을 구할 윈도우 범위)
Deque<Node> deque(데이터를 담을 덱 자료구조)

for(N만큼 반복) {
	now(현재 데이터 값 저장)
	
	// 덱의 마지막 위치에서부터 now보다 큰값 제거
	whlie(deque.getLast().value > now) {
		deque.removeLast();
	}
	
	// 덱의 마지막 위치에 now 저장
	deque.addLast(Node)
	
	// 덱의 1번째 위치에서부터 L의 범위를 벗어난 값 제거 // now 인덱스 - L <= index
	if(deque.getFirst().index < i - L) {
		deque.removeFirst();
	}
	
	// 덱의 1번째 데이터 버퍼에 저장
}

덱에 저장할 노드 클래스 별도 생성
노드 클래스에서 index(자신의 위치), value(자신의 값) 담기

코드 구현하기

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 ) );  
  
       StringTokenizer st = new StringTokenizer( br.readLine() );  
       int N = Integer.parseInt( st.nextToken() );  
       int L =Integer.parseInt( st.nextToken() );  
       
       Deque< Node > deque = new LinkedList<>();  
       
       st = new StringTokenizer( br.readLine() );  
       for ( int i = 0; i < N; i++ ) {  
          int now = Integer.parseInt( st.nextToken() );  
          
          while ( ! deque.isEmpty() && deque.getLast().value > now ) {  
             deque.removeLast();  
          }  
          deque.addLast( new Node( i, now ) );  
          
          if ( deque.getFirst().index <= i - L ) {  
             deque.removeFirst();  
          }  
          
          bw.write( deque.getFirst().value + " " );  
       }  
       
       bw.flush();  
       bw.close();  
    }  
    
    static class Node {  
       public int index;  
       public int value;  
       
       Node(int index, int value) {  
          this.index = index;  
          this.value = value;  
       }  
    }  
  
} // end