백준 15961 회전 초밥(Gold4)

정답코드

import java.io.*;
import java.util.StringTokenizer;

//method 2: sliding Window 접근 
public class Main {
	
	static int [] sushi;
	static int N,d,k,c,maximum;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st =  new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken());  
		d = Integer.parseInt(st.nextToken());  
		k = Integer.parseInt(st.nextToken());  
		c = Integer.parseInt(st.nextToken());  
		maximum = Integer.MIN_VALUE;
		
		
		sushi = new int[N];
		
		for(int i = 0; i < N; i++) {
			sushi[i] = Integer.parseInt(br.readLine());
		}

		slidingWindow();
		System.out.println(maximum);
	}
	
	public static void slidingWindow() {
		
		int []visited = new int[d+1];
		
		//처음 initialize 하는 부분 
		int max, cnt = 0;
		for(int i = 0; i < k; i++) {
			if(visited[sushi[i]] == 0)cnt++; 
			visited[sushi[i]]++;
		}
		
		max = cnt;
		
        //맨 앞 초밥을 빼고 맨 뒤에 초밥을 추가해서 종류 체크
		for(int i = 1; i < N; i++) {
			if(max <= cnt) {
				if(visited[c] == 0) {
					max = cnt+1;
				}else max = cnt;
			}
			
			//sliding window 맨 앞에 거 방문횟수 1개 빼주기 
			visited[sushi[i-1]]--;
			
			//만약에 0이라면 먹은 초밥 종류가 줄어듦 아니라면 그냥 2번 먹은 걸 
			//1번으로 바뀌는 거라서 종류엔 변함 x
			if(visited[sushi[i-1]] == 0)cnt--;
			
			//만약에 얘가 처음방문이면 먹은 초밥 종류가 하나 늘어난 거기 때문에 
			//카운트 해줘야한다
			if(visited[sushi[(i+k-1)%N]] == 0) cnt++;
			visited[sushi[(i+k-1)%N]]++;
		}
		
		maximum = max;
	}

}

전략

• Sliding window를 사용해서 O(NK)복잡도에서 O(N)로 줄여야 한다

• N = 3000000 K = 3000 NK =9000000000번 연산 O(NK)코드로 불가

• O(NlogN) 으로 짜도 33.xxx *3000000 아슬아슬해서 불가능

• int 타입 배열로 각각의 idx로 부터 먹을 수 있는 초밥의 종류를 카운트해서 배열에 넣는다

• window를 이동해가며 앞의 초밥은 제거 뒤의 초밥은 추가해서 초밥의 종류를 따로 카운트

• 쿠폰에 있는 초밥을 먹지 않았다면 1개 더 추가해준다