백준 15961 회전초밥

https://www.acmicpc.net/problem/15961

15961번: 회전 초밥

연속해서 K 개의 초밥을 먹었을때 먹을수 있는 최대의 초밥 종류 갯수를 구하는 문제다.

완전탐색을 이용할 경우 초밥의 접시가 N이 최대 300만개, 연속해서 먹을수 있는 접시의 갯수 k 가 최대 3000이므로

시간복잡도가 O(N*k) = O(300만 * 3000) = O(90억)이므로 시간초과가 난다.

연속하는 경우 수를 구할때는 투포인터를 이용하여 풀면 O(N) 시간 내에 해결할수 있다.

다만 이 문제의 경우 초밥의 종류를 따져야 하므로 Map을 이용하여 탐색, 제거, 추가를 해야한다. Map의 크기가 최대 K이므로 이 문제를 푸는데의 시간 복잡도는 O(N*logK)이므로 이는 시간내에 해결할수 있다.

 

package 백준;
import java.util.*;
import java.io.*;

public class 회전초밥 {
	static class MyScanner {

		BufferedReader bf;
		StringTokenizer st;

		MyScanner() {
			bf = new BufferedReader(new InputStreamReader(System.in));

		}

		String next() {
			if (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(bf.readLine());
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}

			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		MyScanner sc = new MyScanner();
		int N =sc.nextInt();
		int D =sc.nextInt();
		int k =sc.nextInt();
		int c =sc.nextInt();
		int answer = 0;
		int dish [] = new int[N];
		for(int i =0  ;i <N;i++) {
			dish[i] = sc.nextInt();
		}
		
		int l= 0 ;
		int r =0;
		Map <Integer,Integer> map  = new HashMap<Integer,Integer>();
		
		while(l<N) {
			
			if(map.containsKey(dish[(r+N)%N])) { //이미 Map 에 있는 Key면 값만 증가
				int val = map.get(dish[(r+N)%N]);
				map.put(dish[(r+N)%N], val+1);
			}else { //Map에 없는 Key면 1만 증가
				map.put(dish[(r+N)%N], 1);
			}
			
			if(map.containsKey(c)) { //쿠폰이 이미 Map에 포함된 경우
				answer = Math.max(answer, map.keySet().size());
			}else { //쿠폰이 Map에 포함되지 않는 경우
				answer = Math.max(answer, map.keySet().size()+1);
			}
			
			
			if(r-l+1>=k) { //k개 를 채웟으므로 l,r 를 모두 이동 + l를 Map에서 제거
				
				int val = map.get(dish[(l+N)%N]);
				if(val==1) map.remove(dish[(l+N)%N]);
				else {
					map.put(dish[(l+N)%N], val-1);
				}
				l++;
				r++;
			}else { //아직 연속해서 더 먹을 있으므로 r 만 이동
				r++;
			}
			
		}
		
		
		System.out.println(answer);
	}

}