[백준] 2531번 : 회전 초밥

문제

 

 

접근 방식

k개의 초밥을 연속으로 먹었을 때 가장 다양한 종류의 초밥을 먹을 수 있는 경우를

구해야 하는 문제로 초밥을 k개 먹었을 때 중복 되지 않은 초밥이 몇 개인지를 찾으면 된다.

 

탐색은 이전의 투포인터 문제들과 마찬가지로 배열의 첫 인덱스를 기준으로

k개의 초밥을 먹을 때까지 탐색을 하고, 시작 인덱스를 1 증가시켜주면 된다.

// 연속으로 먹은 횟수
// 회전 벨트의 초밥 목록

1	2	3	4k
7	9	7	30	2	7	9	25

	1	2	3	4k
7	9	7	30	2	7	9	25

		1	2	3	4k
7	9	7	30	2	7	9	25

			1	2	3	4k
7	9	7	30	2	7	9	25

				1	2	3	4k
7	9	7	30	2	7	9	25

4k					1	2	3
7	9	7	30	2	7	9	25

3	4k				1	2
7	9	7	30	2	7	9	25

2	3	4k					1
7	9	7	30	2	7	9	25

 

탐색의 진행 과정은 위와 같다.

 

불리언 배열을 이용해 이미 등장한 초밥이라고 기록해두기엔

같은 초밥이 2번 이상 등장 했고, 시작 인덱스가 1 증가할 때마다

기존 시작 인덱스의 초밥을 안 먹었다고 false로 돌리면

해당 초밥을 더 먹었어도 안먹었다고 기록되는 문제가 생겨

정수 배열로 초밥의 등장 횟수를 기록했다.

 

그래서 탐색을 하면서 등장 횟수가 0인 경우에만

현재까지 먹은 종류를 1 증가시켜 주고,

쿠폰으로 얻는 초밥도 현재까지 먹지 않았을 경우에만 종류를 1 증가시켜 준다.

 

또한, 조심해야 할게 회전 초밥이기 때문에

배열의 인덱스를 벗어날 때는 다시 0번째 인덱스로 가게 해줘야 한다.

 

이러한 요소들만 생각하면서 코드를 짜주면 쉽게(여러 번 틀렸지만...) 풀 수 있다.

 

풀이

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[] belt = new int[n];
		int[] types = new int[d + 1];

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

		int end = 0;
		int continues = 0;
		int count = 0;
		int max = 0;

		for (int start = 0; start < n; start++) {
			while (continues < k) {
				if (types[belt[end]] == 0) count++;
				types[belt[end++]]++;
				if (end == n) end = 0;
				continues++;
			}

			if (types[c] == 0) {
				max = Math.max(count + 1, max);
			} else {
				max = Math.max(count, max);
			}

			types[belt[start]]--;
			if (types[belt[start]] == 0) count--;

			continues--;
		}

		System.out.println(max);
	}
}