[백준 - 15961] 회전 초밥 .java

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

 

• 같은 종류 초밥 여러개 가능
• 서로 다른 종류의 k개 접시를 연속해서 먹을 수 있음
• 종류가 c인 초밥을 한번 먹을 수 있음
• 이때 현재 연속된 k개의 접시들 중 c종류 접시가 없으면 종류가 하나 추가됨
• => 먹을 수 있는 초밥의 서로 다른 종류 개수의 최댓값을 구하기
• 원형으로 접시에 접근해야함

 

풀이

고정 길이인 k만큼 윈도우를 설정

=> 초기 윈도우 설정하고 하나씩 이동하며 하나 추가, 하나 삭제

• dishes 배열: 입력받은 순서대로 접시 종류를 저장
• dishCount 배열: 초밥 종류는  2 ≤ d ≤ 3,000 -> 인덱스를 접시 종류로,  값을 현재 윈도우에 속한 초밥 종류의 빈도로 함

=> dishCount의 인덱스가 dishes배열의 값이 되어야함

 

초기 윈도우 설정

후위 연산자를 사용하여 하나 증가하기 전의 현재 접시 빈도가 0이면 없는 종류기 때문에 하나 추가

 

 

추가

if(dishCount[dishes[(i+k-1)%n]]++ == 0) kind++;

i-k+1번째를 추가하면서 원형으로 접근하기 위해 %n

추가하려는 인덱스가 현재 윈도우에 없는 종류라면 하나 추가 -> 후위 연산자 이용

 

 

정답 - 최댓값 갱신

answer = Math.max(answer,kind + (dishCount[c]==0? 1:0));

현재 윈도우가 가지는 종류에 쿠폰에 적힌 접시가 없으면 종류에 하나 추가

만약 있으면(빈도가 0이 아니면) 추가 불가

 

삭제

if(--dishCount[dishes[i]] ==0) kind--;

전위 연산자를 사용하여 빈도를 하나 줄였을 때의 값이 0이라면 

현재 윈도우에 더이상 존재하지 않는 종류기 때문에 종류를 하나 감소

 

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int d = sc.nextInt();
        int k = sc.nextInt();
        int c = sc.nextInt();

        int[] dishes = new int[n];
        for(int i = 0;i < n;i++) {
            dishes[i] = sc.nextInt();
        }

        int[] dishCount = new int[d+1];
        int kind =0;

        for(int i = 0; i<k-1;i++){
            //하나 증가하기 전이 0이면 없던 종류니까 추가
            if(dishCount[dishes[i]]++ == 0){
                kind++;
            }
        }

        int answer = 0;

        for(int i =0; i<n;i++){
            if(dishCount[dishes[(i+k-1)%n]]++ == 0) kind++;

            answer = Math.max(answer,kind + (dishCount[c]==0? 1:0) );

            if(--dishCount[dishes[i]] ==0) kind--;
        }

        System.out.println(answer);

    }
}

 

 

 

길이가 고정된 윈도우(크기 K)

를 한 칸씩 밀면서 탐색할 때

 

• 초기 윈도우 세팅

윈도우에 들어갈 첫 K 개 요소(혹은 필요한 경우 K–1개)를 미리 처리해 두고,그 상태를 기준으로 시작

 

• 매 스텝마다 한 요소 추가 + 한 요소 제거

윈도우의 오른쪽 새로 들어올 요소 하나를 추가(add)

윈도우의 왼쪽 빠져나갈 요소 하나를 제거(remove)

(고정된 크기 K를 유지하면서) 이때마다 필요한만큼 O(1)로 갱신

 

=> 윈도우를 매번 처음부터 다시 계산하는 대신 전체를 O(N) 시간에 한 번만 쭉 이어지면 됨