[백준 2531 : JAVA] 회전 초밥 / 투 포인터

문제

---

 

 

 

풀이

---

투 포인터 알고리즘 기본 유형에 속하는 문제다.

해당 문제에서 유심히 봐둬야할 것은 모듈러(%) 연산을 통해 N-1을 넘어가는 인덱스부터는 0으로 계산되도록 처리한 부분이다.

 

 

 

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
 
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int N, d, k, c;
    private static int[] arr;
    private static int[] eat;
 
    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
 
        eat = new int[d + 1];
        arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
 
        System.out.println( twoPointers() );
 
        br.close();
    }
 
    private static int twoPointers() {
        int count = 0, max;
 
        for (int i = 0; i < k; i++) {
            if (eat[ arr[i] ] == 0) count++; // 처음 먹어보는 종류의 초밥이라면 카운트 + 1
            eat[ arr[i] ]++;
        }
        max = count;
 
        for (int i = 1; i < N; i++) {
            if (max <= count) {
                if (eat[ c ] == 0) max = count + 1;
                else max = count;
            }
 
            eat[ arr[i - 1] ]--;
            if (eat[ arr[i - 1] ] == 0) count--;
 
            if (eat[ arr[(i + k - 1) % N]] == 0) count++;
            eat[ arr[(i + k - 1) % N]]++;
        }
 
        return max;
    }
}