1. 접근
-
주어진 시간은 1초. n은 3만밖에 안되므로 O(n^2)의 케이스로도 처리는 가능하다.
-
결국 하나의 노드는 반드시 다른 하나의 노드만을 가리키기 때문에 배열로 처리해도 상관없다
-
잘 보면 결국 일정한 크기의 윈도우를 옆으로 이동시켜주면 된다
-> 슬라이드 윈도우를 쓰자! -
슬라이드 윈도우의 기본 구조에 따라 가장 초기의 0~k번째 까지의 초밥 연속행을 먼저 구한다
-
이후 윈도우를 옆으로 한칸씩 이동하면서 나가는 값과 들어오는 값으로 인해 변화하는 초밥 종류를 카운트하면 된다
2. 구체화
- 벨트 위에는 같은 종류의 초밥이 둘 이상 있을 수 있다.
- 이 문제에서 가장 고민해야 하는 부분인데, 이 조건만 아니라면 값의 카운트를 bool로 할 수 있지만, 중복을 체크하기 위해 int 값을 쓰게 되었다
- 나가는 값에 의해 생기는 일
- 연속행 숫자의 카운트 배열에서 지금 나가는 값의 카운트를 빼준다
- 만약 지금 나간 숫자가 1개밖에 없는 초밥이었다면, 개수카운트가 0이 되었을 것. 종류 카운트도 1개 빼준다
- 지금 나간 숫자가 개수 카운트에서 0이 되었다면. 나감으로써 쿠폰으로 받을 수 있게 되므로 다시 종류 카운트를 1개 늘려준다
- 들어오는 값에 의해 생기는 일
- 연속행 숫자의 카운트 배열에서 지금 들어온 값의 카운트를 더해준다
- 만약 지금 들어온 숫자가 카운트가 0이었다면 새로운 초밥이 들어왔으므로 종류 카운트를 1개 늘려준다
- 지금 들어온 숫자가 쿠폰 번호였다면. 들어옴으로써 쿠폰을 받을 수 없게 되므로 다시 종료 카운트를 1개 줄여준다
길게 썼지만 나가고 들어오는 방식은 결국 반대 작용이고, 원리는 동일하다
좀더 간단하게 짤수도 있지만 이해하기 쉽게 여러 절차에 나눠서 코드를 짰다
(ex- 들어오고 나가는 초밥이 쿠폰이라면 아예 카운트 자체를 건들지 않을 수도 있다)
3. 나의 코드
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, d, k, c;
cin >> N >> d >> k >> c;
vector<int> table(N);
vector<int> repeatcheck(d+1); //숫자가 있는 개수만큼 값을 넣을 배열
for (int i = 0; i < N; i++) {
cin >> table[i];
}
fill(repeatcheck.begin(), repeatcheck.end(), 0); //배열의 값을 모두 0으로 초기화
int count = 0;
int maxcount = 0;
//가장 초기 값을 한 번만 구한다
for (int i = 0; i < k; i++) {
if (repeatcheck[table[i]] == 0 ) {
count++;
}
repeatcheck[table[i]]++;
}
if (repeatcheck[c] == 0) count++;
maxcount = count;
for (int i = 1 ; i < N; i++) { //회전 시작점을 i라고 하고, 오른쪽으로 슬라이드
int outnum, innum;
outnum = table[(i - 1)%N];
innum = table[(i + k - 1)%N];
repeatcheck[outnum]--; //나가는 숫자의 개수를 빼준다
//쿠폰으로 받는 초밥이 연속행에서 전부 빠졌으면 이제 쿠폰으로 받을 수 있다
if (outnum == c && repeatcheck[outnum] == 0) {
count++;
}
//쿠폰으로 받아야 하는 초밥이 연속행에 들어와버리면 쿠폰으로 못받는다
if (innum == c && repeatcheck[innum] == 0) {
count--;
}
//들어오고 나가는 초밥에 대해 count값을 처리한다
if (repeatcheck[outnum] <= 0) count--;
if (repeatcheck[innum] <= 0) count++;
//새롭게 들어온 값인지 체크하기 위해 뒤에 더해준다
repeatcheck[innum]++;
//그 중 종류의 최댓값을 채택한다
maxcount = max(count, maxcount);
}
cout << maxcount << "\n";
return 0;
}채점 결과
일단 시작하기