[25.03.15] 회전초밥

 

15961

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

// The main method must be in a class named "Main".
class Main {
    static int N;
    static int d;
    static int k;
    static int c;
    static int[] dish ;
    static int[] check;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s= br.readLine().split(" ");
        N = Integer.parseInt(s[0]);
        d= Integer.parseInt(s[1]);
        k = Integer.parseInt(s[2]);
        c = Integer.parseInt(s[3]);
        dish = new int[N];
        check= new int[d+1];
        for(int i=0; i<N; i++){
            dish[i]=Integer.parseInt(br.readLine());
        }
        //연속 먹는 슬라이딩 윈도우 초기화
        for(int i=0; i<k; i++){
            check[dish[i]]++;
        }
        check[c]++;
        int count =0;
        for(int i=1; i<=d; i++){
            if(check[i]>0){
                count++;
            }
        }

        int max = count;
        for(int i=1; i<N; i++){
            int end = (i+k-1)%N;
            check[dish[i-1]]--;
            if(check[dish[i-1]]==0){
                count--;
            }
            if(check[dish[end]]==0){
                check[dish[end]]++;
                count++;
            }
            else{
                check[dish[end]]++;
            }
            max = Math.max(max,count);
        }
        System.out.printf("%d",max);

    }
}

 

문제는 누가봐도 슬라이딩 윈도우 쓰는건 보인다.

 

문제는 N이랑 d , k를 좀 크게 줘서 시간초과 안걸리게 잘 조절해야한다.

 

나는 종류를 구하기 위해서 초밥의 종류 배열(check) 을 선언했다.

 

해당 배열이 1 이상이면 슬라이딩 윈도우 안에 들어가 있는 종류의 초밥인 것이다.

 

그렇다면 종류의 최댓값을 구하기 위해서 매 슬라이딩 윈도우 이동시마다 이 종류 배열을 전부 탐색하면서 1 이상인 갯수를 세줘야하는데... 이게 타임아웃에 걸린다. 바깥에 for문이 이미 돌고있고 안쪽에서 이 배열 탐색에 대한 다시 for문이 돌기에 2중 for문... 

for( N)

for ( d) 이기에 O(N*d) 로 1초에 넘어갈 것이 뻔하다.

 

이 종류를 위해서 큐로 할 수 있지 않을까? 생각했었는데 어찌됐든 현재 슬라이딩 윈도우를 위해서는 큐도 가능은 하지만 굳이 싶었다. 그리고 문제를 풀어보면서 정해진 크기에 대해서는 최대한 배열을 써서 정해진 크기 안에서 코딩을 하는 것이 효율적임을 알고 있었다.

 

매번 종류 배열을 모두 돌면서 count를 셀 순 없기에 슬라이딩 윈도우를 이동하는 순간에 세기로 하였다. 

 

윈도우를 이동하면 슬라이딩 윈도우 오른쪽 한칸이 추가되고 , 왼쪽 한칸이 윈도우에서 빠진다.

 

이때 추가되는 것이 기존 종류배열에서 이미 1 이상이라면 (== 슬라이딩 윈도우에 포함된 초밥 종류) 종류의 갯수는 변함이 없지만 ==0 이라면 새로운 초밥이 윈도우 안에 들어온것이라서 count++ 해준다.

 

마찬가지로 윈도우에서 빠지는 원소는 빠진 후 ==0 이라면 초밥 종류가 하나 빠진것이라 count--해주고 1 이상이라면 똑같은 종류가 윈도우 안에 있는거니까 종류 count에는 변함이 없다.