15961_회전 초밥

사용 알고리즘: 슬라이딩 윈도우

사용 언어: java

 

package ssafyAlgorithm;

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

public class Main_bj_15961_회전초밥 {
	static int n,d,k,c, dishes[], list[];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt(); //접시 개수
		dishes = new int[n];
		
		d = sc.nextInt(); //초밥 가지수
		list = new int[d+1];
		
		k = sc.nextInt(); //연속 접시 수
		c = sc.nextInt(); //쿠폰 번호
		
		for(int i=0; i<n; i++) {
			dishes[i] = sc.nextInt();
		}
		
		list[c]++; //쿠폰은 먹이고 시작
		
		int ans = 0;
		for (int i = 0; i < k; i++) {
			list[dishes[i]]++;
		}
		for (int i = 0; i < list.length; i++) {
			if(list[i] > 0) ans++;
		}
		//
		
		int tmpCnt = ans;
		for (int startDish = 1; startDish < n; startDish++) {
			int prevCnt = tmpCnt;
			
			list[dishes[startDish-1]]--; //지울 거
			if(list[dishes[startDish-1]] == 0) prevCnt--;
			
			int end = startDish+k - 1; //더할 거
			if(end >= n) end = end%n;
			list[dishes[end]]++;
			if(list[dishes[end]] == 1) prevCnt++;
			
			
			ans = Math.max(ans, prevCnt);
			tmpCnt = prevCnt;
		}
		
		System.out.println(ans);
	}

}

 

코드가 아주 더럽구나...

채점하는 데 시간도 오래 걸렸다...

 

처음엔 Map에 집어넣고 map.size()로 구하려고 했는데, 시간 초과 났던 거 같다.

그래서 힌트 참고해서 슬윈으로 만들었는데, list[dishes[startDish-1]]를 처음에 list[startDish-1]로 해서 틀렸고,

prevCnt를 안 쓰고 tmpAns만 써서 또 틀렸다. (이렇게 하면 기존 ans가 4이고, tmpANs가 3일 때, ans는 그대로 4로 남기 때문에 그다음에 tmpAns는 3이 아닌 4로 시작하게 되고 -> 이렇게 되면 원래 답보다 크게 나올 수밖에 없다. 그래서 이를 해결하기 위해 prevCnt를 써서 tmpAns값과 서로 주고 받고 하면서 이 문제를 해결했다 -> 이 부분이 코드가 더러워지는 데 일조를 한 느낌)