[백준] Silver I. 회전 초밥

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

 

문제 유형

• 슬라이딩 윈도우
• 투 포인터

 

코드

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

public class boj2531 {
    static int n, d, k, c;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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());

        int [] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        int [] cnt = new int[d + 1]; // 초밥의 초기 갯수 계산

        int unique = 0;
        for(int i = 0; i < k; i++) {
            if (cnt[arr[i]] == 0) unique++;
            cnt[arr[i]]++;
            // System.out.println(arr[i] + " " + cnt[arr[i]]);
        }

        int max = 0;
        for(int i = 0; i < n; i++) {
            int left = arr[i];
            cnt[left]--;
            if (cnt[left] == 0) {
                unique--;
            }

            int right = arr[(i + k) % n];
            if (cnt[right] == 0) {
                unique++;
            }
            cnt[right]++;

            int cur_len = unique;
            if (cnt[c] == 0) {
                cur_len++;
            }
            max = Math.max(max, cur_len);
        }
        System.out.println(max);
    }
}

 

 

접근 방법

문제에서 주어진 연속해서 먹는 접시 수, k값은 4 입니다.

따라서, 초기 슬라이딩 윈도우 값을 정의할 때 각 접시의 개수를 세줘야 합니다.

 

int [] cnt = new int[d + 1]; // 초밥의 초기 갯수 계산

int unique = 0;
for(int i = 0; i < k; i++) {
    if (cnt[arr[i]] == 0) unique++;
    cnt[arr[i]]++;
}

7	9	30
2	1	1

 

초기 값들을 정의하면 이런 형태로 배열에 등장 횟수가 저장될 것 입니다.

이때, unique한 접시의 갯수는 [7,9,30] 3개 이므로 따로 값을 저장해줍니다.

 

그 다음, 기존 arr 배열을 순회하며 왼쪽, 오른쪽 값들을 각각 업데이트 해줍니다.

int left = arr[i];
cnt[left]--;
if (cnt[left] == 0) {
    unique--;
}

왼쪽 포인터가 가르키는 지점의 등장횟수를 하나씩 제거해야 합니다.

7	9	30
1	1	1

 

처음 배열을 순회한다면, 7의 갯수가 하나 줄어들 것 입니다.

이 때, 등장 횟수가 0이 된다면 해당 접시가 더이상 존재하지 않는 다는 뜻 이므로 unique를 1 빼줘야 합니다.

 

int right = arr[(i + k) % n];
if (cnt[right] == 0) {
    unique++;
}
cnt[right]++;

 

오른쪽일 때를 보면, (i + k)에 n으로 나눠주었습니다. 이 때 n으로 나눠준 것은 접시가 원형 형태로 존재하기 때문에, 배열의 끝에 도달하더라도 이후의 값들을 참조할 수 있어야 합니다. 
ex) [7,0,1,2] 

 

오른쪽 포인터는 반대로, 등장횟수가 0인 접시가 있다면, unique를 1 증가시켜 줍니다.

그리고, 가르키는 배열의 등장횟수를 1 늘려줍니다.

 

7	9	30	2
1	1	1	1

 

2를 가르키고 있으므로, 해당 등장횟수를 늘려줍니다.

 

또 고려해야 할 부분은, 현재 탐색중인 배열에 쿠폰이 포함되어 있는지를 파악해야 합니다.

    int cur_len = unique;
    if (cnt[c] == 0) {
        cur_len++;
    }
    max = Math.max(max, cur_len);

 

쿠폰의 등장횟수가 없다면, 무료로 쿠폰에 해당하는 접시를 먹을 수 있다는 뜻 이므로 현재 길이를 1 늘려줘야 합니다.

 

위의 케이스에선 무료 쿠폰인 30이 포함되어 있으니 길이가 4로 유지됩니다. 
이렇게 한번 탐색이 끝날 때 마다 현재 길이의 최댓값들을 갱신하고, 이 때의 최댓값을 리턴해주면 됩니다.