[JUNGOL 2577] 회전 초밥(고)

http://jungol.co.kr/bbs/board.php?bo_table=pbank&code=2577&sca=99 

JUNGOL

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main_JO_2577 {
	static int N, d, k, c;
	static int[] arr;
	static int answer=0;
	public static void main(String[] args) throws 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());
		arr=new int[N+k-1];
		for (int i=0; i<N; i++) {
			arr[i]=Integer.parseInt(br.readLine());
		}
		for (int i=N; i<N+k-1; i++) {
			arr[i]=arr[i-N];
		}
		window_sliding(k, c);
		System.out.println(answer);

	}
	private static void window_sliding(int window, int coupon) {
		Map<Integer, Integer> map=new HashMap<>();
		map.put(coupon, 1);
		for (int i=0; i<window; i++) {
			int cnt=map.containsKey(arr[i])?map.get(arr[i]):0;
			map.put(arr[i], cnt+1);
			answer=Math.max(answer, map.keySet().size());
		}
		for (int i=window; i<N+k-1; i++) {
			map.put(arr[i-window], map.get(arr[i-window])-1);
			if (map.get(arr[i-window])==0) map.remove(arr[i-window]);
			int cnt=map.containsKey(arr[i])?map.get(arr[i]):0;
			map.put(arr[i], cnt+1);
			answer=Math.max(answer, map.keySet().size());
		}
	}

}

슬라이딩 윈도우 문제다! 라고 직감하고 map을 이용해서 풀었다..

key를 빼고 value값이 0이면 아예 key를 제외하는 처리를 해줬다.

key의 사이즈를 새는 식으로 먹을 수 있는 초밥의 가짓수를 세줬는데, 이렇게 하면 시간이 많이 걸린다.

 

map을 이용하는 대신 배열의 인덱스를 이용해서 푼다면 시간을 반으로 줄일 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
	static int N, d, k, c;
	static int[] arr;
	static int[] check;
	static int answer=0, cnt=0;
	static int num;
	public static void main(String[] args) throws 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());
		arr=new int[N+k];
		check=new int[d+1];	//인덱스=초밥 넘버
		boolean isCoupon=false;
		for (int i=0; i<N; i++) {
			arr[i]=Integer.parseInt(br.readLine());
		}
		for (int i=N; i<N+k; i++) {
			arr[i]=arr[i-N];
		}
		for (int i=0; i<N+k; i++) {
			if (i>=k) {		//줄이기
				num=arr[i-k];
				check[num]-=1;
				if (check[num]==0) {
					cnt--;
					if (num==c) isCoupon=false;
				}
			}
			num=arr[i];
			check[num]+=1;
			if (check[num]==1) cnt++;
			if (num==c) isCoupon=true;
			if (i>=k) {
				answer=Math.max(answer, isCoupon?cnt:cnt+1);
			}
			
		}
		System.out.println(answer);
		
	}

}

슬라이딩 윈도우를 진행시켜 가면서 인덱스가 k 이상이면 앞에꺼를 계속 빼주고,

빼줬는데 해당 초밥 넘버 인덱스의 배열 값이 0이면 count-- 해줘서 가짓수가 줄어들었음을 나타낸다.

추가해주는 것은 check[num]+=1 로 하는데, 이때 값이 1이면 처음 추가된 것이므로 count++ 해줘서 가짓수를 높인다.

 

여기서 포인트는 coupon이 있는지 없는지 flag 값으로 표시해서, 해당 영역에 쿠폰이 포함되어 있으면 count를 answer과 비교하고 포함되어 있지 않으면 count+1을 answer과 비교하는 식으로 진행한다.