[백준OJ] 15961번 회전 초밥

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

15961번: 회전 초밥

---

 

-풀이-

뱀이 이동하는것마냥 문제를 해결했다.

예제를 이용해서 설명을 해보겠다.

먼저 check배열은, 해당 숫자의 음식을 몇번 만났는지를 기록해주는 배열이라고하고, kind변수는 K개의 음식을 먹었을때, 총 몇종류를 먹는지에 대한 변수라고 하자. 그러면 해당 check를 1더해주었을때 1이되면, 처음보는 종류이므로 kind가 1 증가할것이고, 해당 check를 1빼주었을때 0이되면, 해당 숫자의 종류는 사라지는 것이므로 kind가 1 감소할것이다.

 

먼저 입력을 받으면서 쿠폰에 적힌 번호를 체크해주었다. (check[c]++) 그러면, c번호의 음식은 처음만나는 것이므로, 종류가 하나 늘었다( Kind++)

그런뒤, 음식들을 입력받으면서 처음 K개의 음식들에 대한 종류를 카운트 해준다. ( 9,7,30,2 이므로 Kind = 4, 쿠폰은 30이므로 5가아닌 4가된다.)

 

--현재 check배열 상태 ( 편의상 0이 아닌것들만 표시)--

9	7	30	2
1	1	2	1

 

그다음, 최대 종류의 개수를 갱신시켜준 뒤, 맨 뒤의 음식인 9번을 없애주고, 다음번 음식인 7번을 추가해준다. 이때 위에 말했던것처럼 check[9]--를 해준다면, 0이되므로, kind의 값은 1이 감소될 것이다. (현재 kind=3)

또 다음 음식인 7번을 더해주었을때, 이미 7번 음식이 있으므로, kind의 값은 변하지 않는다.

 

--현재 check배열 상태 ( 편의상 0이 아닌것들만 표시)--

7	30	2
2	2	1

 

그다음, 최대 종류의 개수를 갱신시켜준 뒤, 맨뒤의 음식인 7번을 없애주고, 다음번 음식인 9번을 추가해준다.

위와 같은 로직으로 check[7]--를 해주어도 0이 되지않으므로, kind의 값은 변하지 않는다.

check[9]++를 해주면, 1이되므로, kind의 값이 1 증가한다. (현재 kind=4)

 

--현재 check배열 상태 ( 편의상 0이 아닌것들만 표시)--

9	7	30	2
1	1	2	1

 

이런식으로 마지막 경우까지 쭉 구해준 뒤, 갱신된 최댓값을 출력해주면 된다.

 

-시간복잡도-

O(N)

 

-코드-

#include <iostream>
#include<algorithm>
using namespace std;

int n, d, k, c;
int belt[3000001] = { 0 };
int check[3001] = { 0 };
int kind = 0, result = 0;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n >> d >> k >> c;
	check[c]++;//쿠폰
	kind++;//쿠폰으로 인한 종류 1개 증가

	for (int i = 0; i < n; i++) {
		cin >> belt[i];
		//처음K개에 대해서 종류를 체크
		if (i < k) {
			if (check[belt[i]]==0) {//처음만나는 음식이면 kind 1 증가
				kind++;
			}
			check[belt[i]]++;
		}
	}
	result = kind;

	for (int i = 0; i < n; i++) {
		//값 갱신
		result = max(result, kind);

		//종류 바꾸기
		int tail = belt[i];//현재 꼬리
		int head = belt[(i+k)%n];//다음 머리가 될 음식

		//현재 꼬리를 자른뒤, 종류 갱신
		check[tail]--;
		if (!check[tail]) {
			kind--;
		}

		//다음 머리를 추가한뒤, 종류 갱신
		check[head]++;
		if (check[head] == 1) {
			kind++;
		}
	}
	cout << result << "\n";

	

	return 0;
}