15961 - 회전 초밥[G4]

 

문제

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

15961번: 회전 초밥

 

풀이

초밥의 전체 배열이 주어지면, 연속으로 k개를 먹는다고 할 때 얼마나 다양한 접시를 먹을 수 있는가? 최대값을 구하는 문제이다.

 

사실 이 문제는 슬라이딩 윈도우나, 투 포인터를 사용하는 것이 가장 이상적이다.

하지만 이번 풀이에는 이와 유사하게 HashMap을 사용하여 풀이해보았다.

근본적인 로직 자체는 비슷하고, O(3N) 정도의 시간 복잡도를 가질 테였다(해시 충돌이나 이런 걸 배제하고)

 

최악의 엣지 케이스의 경우 N = 300만이었다. 

일반적으로 1초 = 1000만번의 연산으로 가정할 때 거의 시간 초과에 가깝다고 생각했다.

 

결과는 거의 아슬하게 성공. 자세한 내용은 코드를 참고할 것.

 

코드

 

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
    	int res = 0;
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	int N = Integer.parseInt(st.nextToken()); //접시
    	int d = Integer.parseInt(st.nextToken()); //초밥수
    	int k = Integer.parseInt(st.nextToken()); //연속접시
    	int c = Integer.parseInt(st.nextToken()); //쿠폰번호
    	
    	int dish[] = new int[N];
    	for(int i = 0; i < N; i++) dish[i] = Integer.parseInt(br.readLine());
    	
    	
    	//초기 입력
    	HashMap<Integer, Integer> takes = new HashMap<>();
    	for(int i = 0; i < k; i++) {
    		int now = dish[i];
    		if(takes.containsKey(now)) takes.put(now, takes.get(now) + 1);
    		else takes.put(now, 1); 
    	}
    	res = takes.size(); 
    	if(!takes.containsKey(c)) res++;
    	
    	//메인 로직
    	for(int i = 0; i < N + k; i++) {
    		int last = dish[i % N]; //이전 접시
    		int now = dish[(i + k) % N]; //새로운 접시
    		
    		//제거
    		if(takes.containsKey(last)) {
    			if(takes.get(last) == 1) takes.remove(last);
    			else takes.put(last, takes.get(last) - 1);
    		}
    		
    		//추가
    		if(takes.containsKey(now)) takes.put(now, takes.get(now) + 1);
    		else takes.put(now, 1);

    		int nowRes = takes.size();
    		if(takes.containsKey(c)) nowRes++; //쿠폰번호
    		
    		res = Math.max(res, nowRes);
    	}
    	
    	System.out.println(res);
    }
}