백준 2531번 회전 초밥 [JAVA]

2531번: 회전 초밥

 

풀이 방법

손님이 먹을 수 있는 초밥 가짓수의 최댓값을 구하는 문제였습니다.

 

몇 번의 초밥을 먹었는지 확인할 수 있는 배열 : check []

종류별로 몇 개 먹었는지 확인할 변수 : count

 

1) 처음 연속해서 k개를 먹었을 경우 몇 번의 초밥과 종류별로 몇 개 먹었는지 확인

2) start=1, end=k로 한 칸씩 ++하면서 종류별로 먹은 최대 초밥 수 max 변수에 담기

3) start = N 인 경우 즉, 끝까지 확인한 경우 종료

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_BJ_2531_회전초밥 {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int max=0;
        
        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 [] sushi = new int[N];
        for(int i=0;i<N;i++) {
            sushi[i] = Integer.parseInt(br.readLine());
        }
        
        int [] check = new int[d+1];
        int count=0;
        
        for(int i=0;i<k;i++) {
            if(check[sushi[i]]==0) count++;
            check[sushi[i]]++;
        }
        
        max = count;
        int start=1, end=k;
        while(true) {
            
            if(check[sushi[start-1]]==1) count--;
            check[sushi[start-1]]--;
            
            if(check[sushi[end]]==0) count++;
            check[sushi[end]]++;
            
            if(check[c]==0) max = Math.max(max, count+1);
            else max = Math.max(max, count);
            
            start++; end++;
            if(end==N) end=0;
            if(start==N) break;
        }
        System.out.println(max);
            
    }
}