[알고리즘] C++ 백준 2531 회전 초밥

백준 2531

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

2531번: 회전 초밥

풀이 전 나의 생각

회전 초밥의 벨트 상태가 주어졌을 때 쿠폰 초밥과 연속해서 먹을 수 있는 수를 고

려하며 최대 연속해서 먹을 수 있는 초밥의 가짓수를 구해야 한다.

 

조건

1. 원래 회전 초밥은 손님이 마음대로 초밥을 고르고, 먹은 초밥만큼 식대를 계산하지만, 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공한다.
2. 각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의 초밥 하나를 추가로 무료로 제공한다. 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다.
3. 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ k ≤ 3,000 (k ≤ N), 1 ≤ c ≤ d

과정

단순 for문으로만 풀려면 중첩 for문을 굉장히 많이 써야하고 N이 3만까지 가능하기 때문에

시간제한을 맞추지 못한다.

 

따라서 투포인터나 슬라이딩 윈도우 알고리즘을 사용해서 문제를 해결할 수 있다.

 

하지만 이 문제는 슬라이딩 윈도우 알고리즘 보다 투포인터 알고리즘이 훨씬 더 빠른 속도를

보여주기 때문에 투포인터 알고리즘으로 문제를 해결했다. (슬라이딩 300ms ~ 700ms, 투포인터 0ms ~ 4ms)

 

과정은 다음과 같다.

1. 시작 포인터와 끝 포인터를 0, k - 1로 설정한다. 

2. 0부터 k - 1까지 각 초밥의 개수 정보를 넣어주고 중복 되지 않으면 길이 1증가, 중복이라면 넘어간다.

3. 쿠폰 초밥의 개수를 증가시켜주며 1에서 설정한 초밥의 시작과 끝에 쿠폰 초밥이 없다면 길이를 1 증가 시켜준다.

4. 1, 2, 3에서 설정한 초밥의 개수와 길이를 토대로 시작과 끝포인터를

증가시켜주며 k만큼 초밥의 길이를 탐색한다.

 

1번은 k가 4라면 0 ~ 3 즉, k개의 범위만큼 탐색하기 위함이다.

 

2번은 0부터 3까지의 초밥이 7, 9, 7, 30이라면 7이 중복되어 최대 만들 수 있는 길이는 3이다.

 

3번은 시작 초밥이 중복되지 않으면 길이를 감소시키고 끝 초밥이 중복되지 않으면 증가시켜주며

투 포인터를 진행할 때, 초기에 쿠폰 초밥이 미리 있어 개수를 2로 증가시켜 놓거나 길이 1을 증가

시켜주면 이에 따라, 시작 초밥이 쿠폰 초밥일 때, 중복 된 판정이 되기 때문에 초밥의 길이가

감소하지 않고 쿠폰 초밥을 이어서 먹었다는 판정이 된다.

 

4번은 슬라이딩 윈도우처럼 조건을 기준으로 시작 초밥을 빼주고 끝 초밥을 추가해주는
형식으로 탐색을 진행한다.

 

쉽게 말해서 시작 초밥과 끝 초밥의 개수를 기준으로 길이를 이어나갈 수 있는지 없는지 판단하는 과정이다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;

int dish[300001];
int sushi[3001];

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

	int N, d, k, c, ans = 0, cnt = 0, coupon = 1;

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

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

	//0 ~ k까지 초밥의 개수를 카운트 해주면서 중복 되지 않는다면 길이를 증가 시켜준다.
	for (int i = 0; i < k; i++)
	{
		if (++sushi[dish[i]] == 1) cnt++;
	}

	// 쿠폰 초밥의 개수를 증가 시켜주고 쿠폰 초밥이 초기 초밥에 존재하지 않았다면 길이를 증가 시켜준다. 
	if (++sushi[c] == 1) cnt++;

	int start = 0, end = k - 1;

	while (start < N)
	{
		//현재 시작 초밥이 하나라면 길이 감소 및 시작 포인터 증가
		if (--sushi[dish[start++]] == 0) cnt--;
		
		// 끝 포인터 증가, N - 1부터 N + k 까지 탐색이 필요하기 때문에 % N을 해준다.
		end = (end + 1) % N;

		//현재 끝 초밥이 중복 되지 않는다면 길이 증가
		if (++sushi[dish[end]] == 1) cnt++;

		// 시작 초밥과 끝 초밥의 길이를 구하는 과정이 끝난 후, 최대값 갱신
		ans = max(ans, cnt);
	}
	cout << ans;
}