[2531번] 회전 초밥

www.acmicpc.net/problem/2531

2531번: 회전 초밥

풀이 과정

현재 큐에 들어있는 초밥의 개수를 세기 위한 배열 sushi를 선언합니다.

ex) sushi[3] = 2 → 3번 초밥이 2개 들어있다.

 

초밥을 큐에 넣을 때 다음과 같은 요소를 확인합니다.

 

1. 이미 큐에 존재하는 종류의 초밥인가?

 → 맞다면 가지 수는 변하지 않는다.

 → 아니라면 가지 수에 1을 더해준다.

 

2. 쿠폰에 해당하는 초밥인가?

 → 맞다면 bool 변수를 true로 바꿔준다.

 → 아니라면 bool 변수를 false로 바꿔준다.

 

 

초밥을 큐에서 뺄 때 다음과 같은 요소를 확인합니다.

 

1. 나와 같은 초밥이 큐 안에 존재하는가?

 → 맞다면 가지 수는 변하지 않는다.

 → 아니라면 가지 수에 1을 빼준다.

 

2. 쿠폰에 해당하는 초밥인가?

 → 맞다면 bool 변수를 true로 바꿔준다.

 → 아니라면 bool 변수를 false로 바꿔준다.

 

결과를 비교할 때 쿠폰의 사용 유무를 나타내는 bool 변수를 확인합니다.

 → 쿠폰을 이미 사용했다면(true) 최종 가지 수는 변하지 않는다.

 → 쿠폰을 사용하지 않았다면(false) 최종 가지 수에 1을 더한다.

 

 

7 9 7 30 2 7 9 25

위와 같이 초밥이 놓여있습니다.

 

맨 처음 큐에 맨 뒤 3가지 초밥(7, 9, 25)을 넣고 진행합니다.

 

7 삽입 → (7, 9, 25, 7) → 가지 수 계산 → 7 제거

30 삽입 → (9, 25, 7, 30) → 가지 수 계산 → 9 제거

2 삽입 → (25, 7, 30, 2) → 가지 수 계산 → 25 제거

...

 

위 과정을 반복하면서 최대 가지수를 찾아주시면 됩니다.

 

코드

#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>
#include <deque>
#include <queue>
#include <map>

using namespace std;

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

int N, d, k, c;
int sushi[3001];
int arr[30000];
queue <int> q;
int maxAns;
int ans;
bool useCoupon;

void pushSushi(int sh)
{
	q.push(sh);

	if (sushi[sh] == 0)
	{
		ans += 1;
	}

	if (sh == c && !useCoupon)
	{
		useCoupon = true;
	}

	sushi[sh] += 1;
}

void popSushi()
{
	int sh;
	sh = q.front();

	if (sushi[sh] == 1)
	{
		ans -= 1;

		if (sh == c)
		{
			useCoupon = false;
		}
	}

	sushi[sh] -= 1;

	q.pop();
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	maxAns = 0;
	useCoupon = false;

	cin >> N >> d >> k >> c;

	for (int i = 1; i <= d; i++)
	{
		sushi[i] = 0;
	}

	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];

		if (i > N - k)
		{
			q.push(arr[i]);

			if (arr[i] == c)
			{
				useCoupon = true;
			}

			if (sushi[arr[i]] == 0)
			{
				ans += 1;
			}

			sushi[arr[i]] += 1;
		}
	}

	for (int i = 0; i < N; i++)
	{
		int sh;
		sh = arr[i];

		pushSushi(sh);

		if (!useCoupon)
		{
			if (maxAns < ans + 1)
			{
				maxAns = ans + 1;
			}
		}

		else
		{
			if (maxAns < ans)
			{
				maxAns = ans;
			}
		}

		popSushi();
	}

	cout << maxAns << "\n";

	return 0;
}