[슬라이딩 윈도우 + deque] 백준 11003번

 

문제

1. 숫자 배열 크기 + 범위 크기가 주어짐
2. 숫자 배열이 주어짐
3. 숫자배열에서 범위만큼 움직이며, 그때마다 최소값을 저장
문제 조건 : ( 1 <= 범위크기 <= 숫자 개수 <=  5,000,000 ) +  2.4초(제한시간)

 

문제분석

• 범위 크기 이동만큼 최소값 탐색
  • 슬라이딩 윈도우 : 2개의 포인터를 잡고, 이동시키며 최소값 탐색
• 범위크기 및 숫자개수 최대치가 5,000,000이므로 시간복잡도를 O(n) 초과하여 잡을 수가 없음 (시간 초과)
  • 기본 정렬 시간 복잡도 : O(nlogn)
  • 일반적인 정렬알고리즘으로 풀지 못하므로, 덱(deque)을 도입

Deque (덱)
 - 앞쪽에서 추가/삭제 가능, 뒷쪽에서도 추가/삭제 가능
[구조]
    Add    ->                                               -> Remove
                   Front , 값1, 값2, 값3 ..., End
remove <-                                               <- Add

 

예시)
숫자배열 크기 : 5  / 범위크기 : 3 / 숫자배열 : 1 5 2 3 6
(주요 포인트 : 그 다음 deque에 들어오는 값보다 이전에 들어있던 값이 더 크면 삭제 )
ex) (1,1) (2,5) , (3,2) ... 에서 범위가 3이므로 3개묶음으로 가게된다 (그러면 (3,2)가 존재하므로 (2,5)는 최소값이 영영 될수가 없다)

[덱] : (인덱스번호, 값) 
첫번째 : (1,1)             -> 1 추출
두번째 : (1,1) (2,5)    -> 1 추출
세번째 : (1,1) (2,5) (3,2) -> 1 추출 // 3 인덱스의 값이 , 2 인덱스 값보다 작으므로 2인덱스 삭제
네번째 : (3,2) (4,3) -> 2 추출 // 인덱스번호가 4이므로, 첫번째 인덱스는 제거 ( 범위크기 : 3 )
...

 

수도코드

N(데이터 개수), L(최소값을 구하는 범위)
Deque<Node> mydeque (데이터를 담을 덱 자료구조)
배열 선언

for( N 만큼 반복 )
{
    now (현재 데이터값)
    덱의 마지막 위치에서 now보다 큰값 제거
    덱의 마지막 위치에 now값 저장
    덱의 1번째 위치에서부터 L의 범위를 벗어난 값을 덱에서 제거
    덱의 1번째 데이터 출력
}

덱에 저장할 노드클래스 별도 생성
노드 클래스 (index, value) 저장

 

구현

• BufferedWriter
  
  • System.out.print을 사용하여, 제출할경우 시간초과 발생!
  • 버퍼로 모아서 한번에 출력하는 것이 시간 관리에 효율적임 (500만이라는 큰 수의 테스트 과정도 거칠수 있으니..)

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


public class App {
    public static void main(String[] args) throws Exception {
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(buf.readLine());
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int arraySize;
        int range;
        
        
        if (st.hasMoreTokens()){
            arraySize = Integer.parseInt(st.nextToken());
            range = Integer.parseInt(st.nextToken());
        }else{
            System.out.println("StringTokenizer Error!");
            throw new RuntimeException();
        } 
        
        int[] arr = new int[arraySize];
        int now = 0;
        Deque<Node> myDeque = new LinkedList<>();

        st = new StringTokenizer(buf.readLine());
        for(int i =0; i< arraySize; i++){
            
            now = Integer.parseInt(st.nextToken());

            while(!myDeque.isEmpty() && myDeque.getLast().value > now){
                myDeque.removeLast();
            }
            myDeque.addLast(new Node(i, now));

            if (myDeque.getFirst().index <= i-range){
                myDeque.removeFirst();
            }


            bw.write(myDeque.getFirst().value + " ");
        }

        bw.flush();
        bw.close();

        
        
        

    }


    public static class Node{
        private int index;
        private int value;

        public Node(int index, int value){
            this.index = index;
            this.value = value;
        }
    }
}