문제 풀이

투 포인터를 활용한 문제, 연속된 k개의 구간에서 어떤 종류의 초밥이 선택되었는지 기록하는 check배열을 활용한다.
먼저 처음 k개의 구간에서 어떤 종류의 초밥이 선택되었는지 체크하고, 구간을 한칸씩 옮기면서
옮겨진 후 새로운 r의 접시에는 어떤 초밥이 들어있는지, 옮겨진 후 구간에서 벗어난 l의 접시에는 어떤 초밥이 들어 있었는지 체크하면 된다. 새로운 종류의 초밥이 생겼다면 val값을 올려주고
옮겨진 후 구간에서 벗어난 l의 접시에 들어있는 종류의 초밥이 1개 밖에 없었다면 더 이상 손님이 선택한 초밥이 아니므로 val값을 내려준다.
회전 초밥 형식인 원형 이므로 r값이 n 이상일 경우에는 r= r-n의 식을 적용해서 끝과 끝을 이어주면 된다.

문제 링크

boj/2531

소스코드

PS/2531.java

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

    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 {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n,d,k,c;
            n = Integer.parseInt(st.nextToken());
            d = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            int []check = new int[d+1];
            Arrays.fill(check,0);
            ArrayList<Integer> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                list.add(Integer.parseInt(br.readLine()));
            }
            check[c] = 1;
            int val = 1;
            for(int i=0;i<k;i++)
            {
                if(check[list.get(i)]==0)
                    val++;
                check[list.get(i)] ++;
            }
            int ans = 1;
            for(int i = 0 ;i<n;i++)
            {
                int l = i;
                int r = i + k - 1;
                if(r >=n)
                    r= r-n;
                int nr = r + 1;
                if(nr == n)
                    nr= 0;
                if(check[list.get(nr)] == 0) {
                    val++;
                }
                check[list.get(nr)]++;
                if(check[list.get(l)] == 1) {
                    val--;
                }
                check[list.get(l)]--;

                ans = Math.max(ans,val);
            }
            bw.write(Integer.toString(ans));
            bw.flush();
        }
    }