[Java] 백준 2531번: 회전 초밥

[문제 바로 가기] - 회전 초밥

💡 접근 방식

애증의 회전초밥 -.- 1달전에 도전했다가 피 제대로 보고는 도망쳤었는데 코테 준비를 위해 호기롭게 다시 도전했다.

일단 슬라이딩 윈도우로 풀이했으며 옮기는건 크게 어렵지 않았다.
하지만 쿠폰 초밥을 처리하는 로직에서 어려움을 겪었고 https://maivve.tistory.com/311 이 분의 코드를 참고했다!

문제를 어려운 방식으로 풀이하는 경향이 있어 쉬운 풀이도 돌아가는 것 같다. 손으로 적어가면서 가장 간단한 풀이를 찾아봐야지.

풀이

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		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 arr[] = new int[N];
		int sushi[] = new int[d + 1];
		
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		int start = 0;
		int end = k - 1;
		int count = 0;
        int max = 0;
        
		for (int i = start; i <= end; i++) {
			if (sushi[arr[i]] == 0) count++;
			sushi[arr[i]]++;
		}
		
		while (start < N) {
			if (max <= count) {
				if (sushi[c] == 0) max = count + 1;
				else max = count;
			}
			
			if (sushi[arr[start]] == 1) count--;
			sushi[arr[start]]--;
			
			start++;
			end = (end + 1) % N;
			
			if (sushi[arr[end]] == 0) count++;
			sushi[arr[end]]++;
		}
		
		System.out.println(max);
	}
}