[JAVA] 백준 (골드4) 15961번 회전 초밥

링크

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

---

입력 예제

8 30 4 30
7
9
7
30
2
7
9
25

---

출력 예제

5

---

풀이

일정한 개수에 대하여 연속된 초밥의 종류가 최대일 때의 개수를 구해야 한다. 접시의 수가 최대 3,000,000이므로 매우 크고, 연속되고 일정한 크기의 배열인 조건이 있기 때문에 시간 복잡도 $O(n)$의 슬라이딩 윈도우를 사용한다.

우선 회전 초밥의 원형 벨트를 구현하기 위해 접시 배열은 N+k-1의 크기로 구현한다.

int[] plate = new int[N + k - 1];
for (int i = 0; i < N; i++) {
    plate[i] = Integer.parseInt(br.readLine());
}

for (int i = N; i < N + k - 1; i++) {  //원형 벨트 구현
    plate[i] = plate[i - N];
}

처음 연속으로 초밥을 선택할 때를 기준으로 초밥 종류의 개수를 구한다. 그리고 시작 인덱스, s를 한 칸씩 증가시키면서 제거된 초밥, plate[s - 1]의 개수를 -1하고, 추가된 초밥, plate[s + k - 1]의 개수를 +1한다. 그리고 현재 선택한 초밥에서 쿠폰 적용이 가능할 경우 +1를 해준다.

//크기가 k인 슬라이딩 윈도우
for (int s = 1; s < N; s++) {
    int removedChobab = plate[s - 1];
    int addedChobab = plate[s + k - 1];
    
    chobab[removedChobab]--;  //초밥 제거
    if (chobab[removedChobab] == 0) {  //제거된 초밥의 종류가 없을 때
        count--;
    }
    
    chobab[addedChobab]++;  //초밥 추가
    if (chobab[addedChobab] == 1) {  //추가된 초밥의 종류가 처음일 때
        count++;
    }
    
    if (chobab[c] == 0) {  //쿠폰 적용이 가능할 경우
        chobabCount.add(count + 1);
    } else {
        chobabCount.add(count);
    }
}

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;

/*
백준 / 회전 초밥 / 골드4
https://www.acmicpc.net/problem/15961
 */
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[] chobab = new int[d + 1];
        int[] plate = new int[N + k - 1];
        for (int i = 0; i < N; i++) {
            plate[i] = Integer.parseInt(br.readLine());
        }

        for (int i = N; i < N + k - 1; i++) {  //원형 벨트 구현
            plate[i] = plate[i - N];
        }

        //처음 연속으로 초밥을 선택할 때
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < k; i++) {
            set.add(plate[i]);
            chobab[plate[i]]++;
        }

        List<Integer> chobabCount = new ArrayList<>();

        int count = set.size();  //초기 초밥의 종류
        if (chobab[c] == 0) {  //쿠폰 적용이 가능할 경우
            chobabCount.add(count + 1);
        } else {
            chobabCount.add(count);
        }

        //크기가 k인 슬라이딩 윈도우
        for (int s = 1; s < N; s++) {
            int removedChobab = plate[s - 1];
            int addedChobab = plate[s + k - 1];

            chobab[removedChobab]--;  //초밥 제거
            if (chobab[removedChobab] == 0) {  //제거된 초밥의 종류가 없을 때
                count--;
            }

            chobab[addedChobab]++;  //초밥 추가
            if (chobab[addedChobab] == 1) {  //추가된 초밥의 종류가 처음일 때
                count++;
            }

            if (chobab[c] == 0) {  //쿠폰 적용이 가능할 경우
                chobabCount.add(count + 1);
            } else {
                chobabCount.add(count);
            }
        }

        int max = 0;
        for (Integer i : chobabCount) {
            max = Math.max(max, i);
        }

        System.out.println(max);
    }
}