2012 한국정보올림피아드 시.도지역본선 고등부 2번 회전초밥(BOJ: 2531) 풀이

분류 : 큐, 시뮬레이션

 

초밥의 회전을 나머지연산을 이용하여 인덱싱을 간편하게 할 수 있습니다.

초기세팅

1.     0부터 k개의 초밥번호를 Q에 넣는다 (7,9,7,30)

2.     하나씩 넣으면서 (초밥종류배열[초밥[i]]==0) 이라면 cnt++ 한다.

3.     초밥종류배열[초밥[i]]++ 한다.

4.     Max = cnt;

5.     (초밥종류배열[쿠폰초밥] == 0) 이라면 max +1 한다

6.     end = k-1

N번 반복

1.     Dequeue한다(U). 초밥종류배열[U]-- 한다.

2.     초밥종류배열[U]==0 이라면 cnt--한다.

3.     end = (end+1)%N   //이부분이 중요 회전초밥 이므로 끝이라면 다시 앞으로 가야함.

4.     초밥종류배열[초밥[end]]==0 이라면 cnt++한다.

5.     초밥종류배열[초밥[end]]++;

6.     if(초밥종류배열[쿠폰초밥]==0) -> cnt+1 > max -> max = cnt+1;

else  cnt > max -> max = cnt;

#include <stdio.h>

int flg[3001];
int data[30001];
int N,d,k,c;
int main() {
	//freopen("Text.txt", "r", stdin);
	scanf("%d %d %d %d", &N, &d, &k, &c);
	for (int i = 0; i < N; i++) {
		scanf("%d", &data[i]);
	}
	int sum=0;
	int max;
	for (int i = 0; i < k; i++) {
		if (flg[data[i]] == 0) {
			sum++;			
		}
		flg[data[i]]++;
	}
	max = sum;
	if (flg[c] == 0) {
		max++;
	}

	int start = 0;
	int end = k - 1;
	for (int i = 0; i < N - 1; i++) {
		flg[data[start]]--;
		if (flg[data[start]] == 0) {
			sum--;
		}
		start++;
		end = (end + 1) % N;
		if (flg[data[end]] == 0) {
			sum++;		
		}
		flg[data[end]]++;
		if (flg[c] == 0) {
			if (sum + 1 > max) {
				max = sum + 1;
			}
		}
		else {
			if (sum > max) {
				max = sum;
			}
		}
	}
	printf("%d\n", max);

	return 0;
}