📝 문제 정보#
문제#
러시아워입니다! 오늘 퇴근 후, 쇼핑몰이 닫기 전에 가족 모두에게 줄 사탕을 사야 합니다.
가족들은 독점성과 균일성을 매우 중요하게 여기기 때문에, 당신은 그들을 감동시키기 위한 계획을 세웠습니다. 각 가족 구성원에게 주는 사탕은 모두 단일 브랜드여야 하며, 동일한 브랜드의 사탕을 다른 가족 구성원이 받아서는 안 됩니다. 또한, 누군가를 더 사랑한다는 사실을 들키고 싶지 않기 때문에 모든 가족 구성원이 같은 수의 사탕을 받아야 합니다.
쇼핑몰에는 $K$가지 서로 다른 브랜드의 사탕을 파는 가게가 있습니다. 공교롭게도, 당신의 가족 구성원 수도 정확히 $K$명입니다. 너무 쉬워 보일 수 있지만, 물론 함정이 있습니다.
가게에는 사탕들이 하나의 진열대에 일렬로 놓여 있습니다. 사탕을 하나씩 고를 시간이 없기 때문에, 효율적으로 구매를 완료하기 위해 연속된 구간의 사탕을 한꺼번에 사려고 합니다. 즉, 어떤 두 사탕을 구매할 때, 그 사이에 있는 모든 사탕도 함께 구매해야 합니다.
구매할 수 있는 사탕의 최대 개수는 얼마입니까?
입력#
첫 번째 줄에 두 정수 $N$과 $K$ ($1 \leq N, K \leq 4 \times 10^5$)가 주어지며, 각각 진열대에 놓인 사탕의 수와 가족 구성원의 수를 나타냅니다. 사탕 브랜드는 $1$부터 $K$까지의 서로 다른 정수로 식별됩니다.
두 번째 줄에 $N$개의 정수 $C_1, C_2, \ldots, C_N$ ($1 \leq C_i \leq K$, $i = 1, 2, \ldots, N$)이 주어지며, 진열대에 왼쪽에서 오른쪽 순서로 각 사탕의 브랜드를 나타냅니다.
출력#
구매할 수 있는 사탕의 최대 개수를 나타내는 정수를 한 줄에 출력합니다. 어떤 가족 구성원도 두 가지 다른 브랜드의 사탕을 받을 수 없으며, 어떤 브랜드의 사탕도 두 명의 가족 구성원을 위해 구매될 수 없음을 기억하십시오. 또한, 모든 가족 구성원은 같은 수의 사탕을 받아야 하며, 사탕은 진열대에서 연속된 구간으로 구매해야 합니다.
🧐 관찰 및 접근#
- $N < K$면 펑이고
- 파라메트릭이 되나?
- 아냐 단조성이 없으셔
- 답이 될수있는 길이는 $N/K$에 바운드되는 것 같다
- 루트질 되나
- 2.5억이면 믿어보자
- 아니근데 $K$가 작으면 이슈가 생긴다
- 버킷질…
- 아? 이럴때는 그냥 cnt를 배열로 통째로 관리하자
- 루트질로 뚫어버려
- 아니 같은 풀이를 해싱으로 하면 훨씬 빠르네 ㄱ-
💻 풀이#
- 코드 (C++):
void solve(){
int N, K; cin >> N >> K;
vector<int> v(N);
rep(i, 0, N) cin >> v[i];
rep(i, 0, N) v[i]--;
const int sq = 300;
if(K < sq){
array<int, sq> cnt;
map<array<int, sq>, int> mp;
mp[cnt] = -1;
int ans = 0;
rep(i, 0, N){
cnt[v[i]]++;
bool flag = true;
rep(j, 0, K) if(cnt[j] == 0){
flag = false;
break;
}
if(flag) rep(j, 0, K) cnt[j]--;
if(mp.count(cnt)) ans = max(ans, i - mp[cnt]);
else mp[cnt] = i;
}
cout << ans;
return;
}
vector<int> cnt(K, 0);
int mxCandy = N/K;
rep(i, 0, N) cnt[v[i]]++;
rep(i, 0, K) mxCandy = min(mxCandy, cnt[i]);
rrep(i, 0, mxCandy + 1){
fill(all(cnt), 0);
int mn = N, mx = 0;
int sz = i * K;
rep(j, 0, sz) cnt[v[j]]++;
rep(j, 0, K){
mn = min(mn, cnt[j]);
mx = max(mx, cnt[j]);
}
if(mn == mx){
cout << sz;
return;
}
rep(j, sz, N){
if(v[j-sz] == v[j]) continue;
if(--cnt[v[j-sz]] < mn) mn = cnt[v[j-sz]];
if(++cnt[v[j]] > mx) mx = cnt[v[j]];
if(mn == mx){
cout << sz;
return;
}
}
}
cout << 0;
}