BOJ 2531 : 회전 초밥

#BOJ 2531 : 회전 초밥

2531번: 회전 초밥

#풀이

투포인터를 활용하여 풀 수 있는 문제이다.

예제1)

8 30 4 30
7
9
7
30
2
7
9
25

k 가 4 이므로 

첫번째로 확인하는 수열이 7 9 7 30 이다. 총 3종류의 초밥을 먹을 수 있다(쿠폰 포함)

9 7 30 2 -> 4종류(쿠폰포함)

.

.

. 

이렇게 한칸 식 보면서 종류를 확인할 수 있다.

 

회전초밥 특성상 시작과 끝이 없으므로 배열의 마지막원소 다음은 첫번째 원소가 올 수 있도록 한다.(원형 연결 리스트)

중복된 초밥을 확인하는 vis 배열

지금까지 먹은 초밥 종류의 개수 sushi

 

초밥을 먹을 때마다 vis배열를 증가시키고 vis값이 0 일 때 sushi 를 증가시키고

다음 수열로 넘어갈 때 vis[v[ptr1]]의 값이 1 일 때 만  sushi를 감소시킨다.

 

#코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n, d, k, c;
vector<int>v;
int vis[3001];
int ans = 1;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> d >> k >> c;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		v.push_back(num);
	}
	for (int i = 0; i < n; i++) {
		v.push_back(v[i]);
	}
	int ptr1 = 0;
	int ptr2 = 0;
	vis[c] = 1;
	int sushi = 1;
	while (ptr1 < n) {
		if (ptr2 - ptr1== k) {
			ans = ans < sushi ? sushi : ans;
			if (vis[v[ptr1]] == 1) {
				sushi--;
			}
			vis[v[ptr1]]--;
			ptr1++;
		}

		if (vis[v[ptr2]] == 0) {
			sushi++;
		}
		vis[v[ptr2]]++;
		
		ptr2++;
		
	}

	cout << ans << '\n';
	return 0;
}