BOJ 2531, 15961 : 회전 초밥

알고리즘 문제 전체 링크

 

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

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

 

 

BOJ 2531 : 2 ≤ N ≤ 30,000

BOJ 15961 : 2 ≤ N ≤ 3,000,000

 

초밥의 종류가 가장 최대가 되도록 모두 구해보면 된다.

이 과정에서 슬라이딩 윈도우를 사용해야 N이 3,000,000인 경우에도 시간 내에 처리할 수 있다.

 

초밥 벨트에 놓인 접시를 담을 배열 arr와 먹은 초밥을 저장할 table 배열을 선언하자.

초밥의 가짓수가 최대 3000이므로 3000이상으로 잡는다.

int arr[3010000];
int table[3100];

 

회전 초밥이기 때문에 arr의 N ~ N + k 까지 앞부분의 초밥을 추가한다.

for (int i = 0; i < N; i++) scanf("%d", &arr[i]);
for (int i = N; i < N + k; i++) arr[i] = arr[i - N];

 

coupon에 해당하는 초밥은 무료로 제공하므로 table[coupon] = 1로 표시해둔다.

그리고 최초 k 접시까지 먹은 초밥의 개수를 센다.

이때, ++table[arr[i]] == 1인 경우에만 count를 한다.

table[c] = 1; /* 쿠폰을 처리 */

tmp = 0;
for (int i = 0; i < k; i++)
	if (++table[arr[i]] == 1) tmp++;

++table[arr[i]] == 1이란 것은 table[arr[i]] == 0 이었다는 뜻이 된다.

즉, 아직 먹지 않은 초밥이므로 count 한다.

 

++table[arr[i]] != 1이라면, 이미 연속해서 먹은 초밥에 포함되었으므로 tmp를 증가하지 않는다.

 

최초로 k가 되는 접시에 대한 초밥의 종류를 정하였으므로, max를 tmp로 초기화로 잡고 한 칸씩 이동한다.

table[arr[i -1]] 은 연속한 초밥 k개 중 가장 처음 먹은 초밥이다. 따라서 옆으로 이동할 때 빼게 된다.

빼고난 후 이 값이 0이라면 현재 접시에 없으므로 tmp를 감소한다.

그리고 arr[i + k - 1]의 초밥을 추가한다.

이때, table이 1이 된다면 접시에 없는 초밥이므로 tmp를 증가한다.

그리고 max를 갱신한다.

 

코드로 구현하면 아래와 같다.

max = tmp;
for (int i = 1; i <= N; i++)
{
	table[arr[i - 1]]--; /* 가장 앞의 초밥을 뺀다. */
	if (table[arr[i - 1]] == 0) tmp--; /* table에 0이면 연속해서 먹은 초밥에 없다. */

	table[arr[i + k - 1]]++; /* 가장 뒤에 초밥을 추가한다. */
	if (table[arr[i + k - 1]] == 1) tmp++; /* table이 1이면 신규로 추가된 초밥이다. */

	if (tmp > max) max = tmp;
}

---

문제에서 제시한 예제 1을 그림으로 보면 아래와 같다. (쿠폰 30번)

tmp 중 가장 큰 값이 4이고, 쿠폰을 사용해서 먹는 초밥 30번이 있으므로 답은 5가 된다.

 

예제 2의 경우는 아래와 같다.

tmp 중 가장 큰 값이 3이므로, 쿠폰을 사용해서 먹는 초밥 7번을 포함해 답이 4가 된다.

 

위의 과정에서 초밥이 빠졌을 때, 아직 테이블에 있는지를 판단하는 것이 아래의 코드가 된다.

table[arr[i - 1]]--; /* 가장 앞의 초밥을 뺀다. */
if (table[arr[i - 1]] == 0) tmp--; /* table에 0이면 연속해서 먹은 초밥에 없다. */

 

그리고 초밥이 추가될 때, 이미 테이블에 있는지를 판단하는 것이 아래의 코드가 된다.

table[arr[i + k - 1]]++; /* 가장 뒤에 초밥을 추가한다. */
if (table[arr[i + k - 1]] == 1) tmp++; /* table이 1이면 신규로 추가된 초밥이다. */

 

최종 코드는 아래와 같다.

#include <stdio.h>

int N, d, k, c;
int arr[3010000];
int table[3100];

int main(void)
{
	int max, tmp;

	scanf("%d %d %d %d", &N, &d, &k, &c);

	for (int i = 0; i < N; i++) scanf("%d", &arr[i]);
	for (int i = N; i < N + k; i++) arr[i] = arr[i - N];

	table[c] = 1; /* 쿠폰을 처리 */

	tmp = 0;
	for (int i = 0; i < k; i++)
		if (++table[arr[i]] == 1) tmp++;

	max = tmp;
	for (int i = 1; i <= N; i++)
	{
		table[arr[i - 1]]--; /* 가장 앞의 초밥을 뺀다. */
		if (table[arr[i - 1]] == 0) tmp--; /* table에 0이면 연속해서 먹은 초밥에 없다. */

		table[arr[i + k - 1]]++; /* 가장 뒤에 초밥을 추가한다. */
		if (table[arr[i + k - 1]] == 1) tmp++; /* table이 1이면 신규로 추가된 초밥이다. */

		if (tmp > max) max = tmp;
	}

	printf("%d\n", max + 1);

	return 0;
}