정올 2577 - 회전초밥 고!

jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1838&sca=99&sfl=wr_hit&stx=2577

JUNGOL

 

  오늘 처음보는 문제 유형을 풀었기에 포스팅합니다.

 

  바로바로 '슬라이딩 윈도우'라는 기법으로 풀어야하는 문제입니다.

 

  제가 생각하는 슬라이딩 윈도우는 특정 크기의 array를 옮기면서 메모리를 아끼고 수행 속도도 O(N)으로 컴팩트한 알고리즘이었지만, 이번 문제를 풀면서 그런 제한된 환경에 국한되지 않고 한칸씩 이동할 때마다 특정 array 등을 갱신하는 것 또한 슬라이딩 윈도우 기법이라는 것을 알았습니다.

 

  코드는 아래와 같습니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// 슬라이딩 윈도우 기법 사용할 것.
// set으로는 구현 불가능.
// int[] check를 사용할 것.
// 특정 칸을 들고 이동하는 것 뿐만 아니라 한칸씩 이동할 때마다 특정 array 등을 갱신하는 것 또한 슬라이딩 윈도우 기법임.
public class Main {

	private static int N, d, k, count;
	private static int c;
	private static int[] belt;
	private static int[] check;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer tk = new StringTokenizer(br.readLine(), " ");
		
		N = Integer.parseInt(tk.nextToken());
		d = Integer.parseInt(tk.nextToken());
		k = Integer.parseInt(tk.nextToken());
		c = Integer.parseInt(tk.nextToken());

		belt = new int[N];
		check = new int[d+1];
		
		for(int i = 0; i < N ; i++) belt[i] = Integer.parseInt(br.readLine());
		
		int size = 0;
		for(int i = 0; i < k ; i++) {
			if(check[belt[i]] == 0) size++;
			check[belt[i]]++;
		}
		
		count = size;
		
		for(int i = 1; i < N; i++) {
			check[belt[i-1]]--;
			if(check[belt[(i-1) % N]] == 0) size--;
			
			if(check[belt[(i-1+k) % N]] == 0) size++;
			check[belt[(i-1+k) % N]]++;
			
			if(check[c] != 0) count = Math.max(count, size);
			else count = Math.max(count, size+1);
		}
		
		System.out.println(count);
	}

}