[JAVA] 백준 15961,2531 회전 초밥

15961번: 회전 초밥

2531번: 회전 초밥

15961과 2531은 범위만 다를 뿐, 같은 문제

---

풀이 방법

예제 입력1을 기준으로 설명하려고 한다.

이를 배열로 옮겨보자. 

초밥을 k개(=4개)씩 묶어보면 (7,9,7,30),(9,7,30,2),(7,30,2,7),(30,2,7,9),(2,7,9,25),(7,9,25,7),(9,25,7,9),(25,7,9,7) 이 모두 가능한 경우의 수이다.

여기서 (7,9,25,7),(9,25,7,9),(25,7,9,7) 부분은 index=0과 index=7이 이어져있기 때문에 가능한 경우의 수이다.

편하게 계산해주기 위해서 앞에 k-1개(index=0~2)를 초밥 리스트 뒤에 붙여줄 수 있다. 

 

붙여준 후, 최종적으로 우리가 계산에 사용해줄 초밥 리스트

index의 범위는 0<= index <N+k-1

여기서 우리는 슬라이딩 윈도우라는 기법을 쓸건데, 간단히 말하자면 범위(k=4)를 지정하고 그 범위를 한칸씩 옆으로 밀어 이동시키면서 값을 확인하는 방법이다. 

예를 들어 (7,9,7,30) 구간을 확인하기 위해 index=0 ~ k-1 구간에 있는 초밥들만 확인하는 것이다. 

그림 1

다음으로 (9,7,30,2)를 보기 위해 윈도우를 한칸 옆으로 옮겨준다. (index=1~1+k-1)

이런식으로 윈도우의 index가 N-1이 될 때까지 반복해주면 모든 범위를 구할 수 있다. 

그림 2

그림 1일때 윈도우안에 있는 초밥의 종류는 3개 (7,9,30) 

그림 2일때 윈도우안에 있는 초밥의 종류는 4개 (9,7,30,2) 

그림 2의 초밥 종류를 셀때는 이전 초밥 종류개수(그림 1) - 삭제된 초밥개수(7) + 추가된 초밥개수(2) 을 하면 되는데,  

이때 삭제된 초밥 개수는 무조건 빼는 것이 아니라 현재(그림2) 윈도우에 삭제된 초밥과 같은 종류가 있다면, 빼지 않아도 된다.

 

만약 무조건 삭제된 초밥의 개수를 뺀다면 그림2의 초밥 개수는 (9,30,2)로 3개가 될 것이다.

우리는 추가되거나 빠진 초밥의 개수만 처리할 것이기 때문이다. 중간에 있는 초밥은 신경쓰지 않는다. 

 

그럼 초밥의 개수를 한번 구해보자!

초기 : 초밥의 최대개수 7,9,30 -> 3개

9,7,30,2 -> 4개

7,30,2 -> 3개

30,2,7,9 -> 4개

2,7,9,25 -> 4개

7,9,25 -> 3개

9,25,7 -> 3개

25,7,9 -> 3개

모두 구해보면 구할 수 있는 초밥의 개수는 최대 4개이다.

하지만, c에 적힌 초밥은 무조건 추가시킨다고 했기 때문에 초기에 초밥의 개수를 구할 때 무조건 1을 더해준다.

따라서 최대 초밥의 개수는 5가 된다. 

 

중복 검사를 하기 위해서 계수정렬 방식으로 초밥의 가짓수(d)만큼 배열을 만들어서, 윈도우 범위 안에 있는 초밥의 종류 index를 이용한다. 

 

정리 

1. 슬라이딩 윈도우 이용

2. 중복된 초밥 구하기 위해 초밥의 가짓수만큼 배열을 만들어 초밥의 종류 index를 활용한다.

3. 초밥의 max값을 구하기 전, c에 적인 초밥의 종류를 +1 해준다. 따라서 max의 초기값은 1이 초밥의 종류 index에도 +1이 될 것이다. 

4. 초기 슬라이딩 윈도우에서의 초밥의 max값을 구한다

   (현재 초밥의 개수 = 이전 초밥 개수 - 삭제된 초밥 + 추가한 초밥 / 삭제된 초밥 개수는 무조건 빼는 것 X, 현재 윈도우 안에 삭제된 초밥이 있다면, 빼지 않아도 됨)

5. 윈도우를 한칸씩 옮겨가며 그때마다 초밥의 max값을 갱신해준다. 

 

JAVA 코드

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

public class BOJ_15961_회전초밥 {
	static StringTokenizer st;
	static StringBuilder sb=new StringBuilder();
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		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[] list=new int[N+k-1];
		for (int i = 0; i < N; i++) {
			list[i]=Integer.parseInt(br.readLine());
		}// 입력완료
		
		for (int i = 0; i < k-1; i++) {
			list[N++]=list[i];
		}

		int[] eaten=new int[d+1];
		int max=1; // 쿠폰 먹었다고 치자
		eaten[c]+=1;
		
		// 처음 
		int start=0;
		for (int i = start; i < k; i++) {
			if(eaten[list[i]]==0) {
				max++;
			}
			eaten[list[i]]+=1;
		}
		
		// 윈도우 이동
		start=0;
		int end=k;
		
		int result=max;
		for (int i = end; i < list.length; i++) {
			eaten[list[start]]-=1;
            // 삭제된 초밥 개수는 무조건 빼는 것 X, 현재 윈도우 안에 삭제된 초밥이 있다면, 빼지 않아도 됨
			if(eaten[list[start]]==0) {
				result-=1;
			} // 전처리
			// 추가된거 처리
			if(eaten[list[i]]==0) result+=1;
			eaten[list[i]]+=1;
			max=Math.max(max, result);
			start++;
		}
		
		System.out.println(max);
	}
}

슬라이딩 윈도우