[Codeforces 1163B2] Cat Party (Hard Edition)

[Codeforces 1163B2] Cat Party (Hard Edition) - 1700

문제 설명 : 

n개의 숫자가 주어진다. 등장한 숫자가 모두 같은 빈도수로 등장하는 가장 큰 지점(인덱스)을 찾아야 하는데, 딱 1개의 아무 숫자를 삭제할 수 있다(반드시 1개를 삭제해야만 한다). 

풀이 : 

이 문제에서 정답이 될 수 있는 케이스가 크게 4가지가 존재한다. 

1. 단 한 가지의 수만 등장할 때

2. 여러 가지의 수가 딱 1번씩만 등장할 때

3. 한 가지의 수가 나머지 등장한 수들의 등장 횟수보다 딱 1번 더 많이 등장할 때 

4. 한 가지의 수만 1번 등장하고 나머지 수들은 모두 그보다 1번보다 더 많이 등장할 때

이렇게 분류할 수 있다. 1~4번 모두 관건은 각 숫자를 볼 때 지금껏 등장한 수들이 모두 같은 빈도 수로 등장했는지를 판별하는 것이 중요하다. 이 문제의 Easy version은 등장하는 수의 범위가 1~10까지 밖에 안되기 때문에 10개를 다 살필 수 있었지만 ( 시간복잡도 O(N*M) ) Hard Version의 경우 범위가 1~10만이기 때문에 이 방법을 사용할 수 없다. 이를 해결하기 위해서 사용하는 것이 'stl set'이다. 

set의 템플릿으로는 pair<int,int>를 사용한다. pair의 first는 인덱스(second)의 빈도 수, second는 인덱스를 저장할 것이다. 그리고 pair의 default 연산상으로 pair의 first를 오름차순으로 정렬됨을 이용할 것이다. 따라서 set에 저장되는 방식은 빈도수가 작은 인덱스일수록 앞쪽에 정될 것이다. 그래서 가장 많이 등장한 빈도수(코드 상에서 변수 mx)는 set의 가장 마지막에 저장될 것이라서 rbegin()->first가 되고( rbegin()함수는 가장 마지막 원소를 가리키는 iterator라고 보면 된다), 가장 적게 등장한 빈도수(mn)은 set의 가장 첫 번째인 begin()->first가 될 것이다. 위의 1,2번 케이스의 경우는 간단하게 생각하면 된다. 1번 케이스는 set의 size가 1이면 해당하는 것일테고, 2번 케이스는 mn과 mx만 같은지 확인하면 그 사이의 빈도수도 반드시 같을 것이라고 보장된다. 중요한 것은 3,4번 케이스의 분류인데 이다. 3번 케이스의 경우 일단 mn+1==mx를 만족해야 하고 나머지 원소들의 빈도수가 mn인지 확인하기 위해서는 ( mn*size+1 == i )가 성립하는지 확인하면 된다. 간단한 샘플 데이터를 만들어보면 쉽게 확인할 수 있다. 비슷한 원리로 4번 케이스는 ( mx*(size-1)+1 == i )인지 확인하면 된다.

주의할 점 : 

-

배운 점 : 

n개의 수들이 모두 같은 빈도수로 등장했는지 판별하는데 최대 빈도수와 최소 빈도수, 그리고 set의 size를 활용함으로써 O(logN)만에 구할 수 있다.

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,int> Cord;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b;
 
    S(){}
    S(int _a,int _b){
        a=_a;
        b=_b;
    }
 
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int,vector<int>,greater<int>> mpq;
#define SPACE 0
#define NL 1
inline void showAll(vector<int> &v,int NL_or_space){ 
    //0 is space, 1 is NL
    for(int &here:v){
        printf("%d",here);
        printf("%c",(NL_or_space)?'\n':' ');
    }
}
/*********************Contest Template***********************/
const int SIZE=100009;
 
set<pii> sii;
int cnt[SIZE]={0};
 
int main(){
    int n;  scanf("%d",&n);
 
    int ans=0;
    for(int i=1 ; i<=n ; i++){
        int inp;    scanf("%d",&inp);
 
        sii.erase({cnt[inp],inp});
        sii.insert({++cnt[inp],inp});
        if(sii.size()==1)
            if(i<n){
                ans=i+1;
                continue;
            }
 
        int mx=sii.rbegin()->first;
        int mn=sii.begin()->first;
 
        if(mx==mn && i<n) ans=i+1;
        else if(mx==mn+1 && mn*sii.size()+1 == i) ans=i;
        else if(mn==1 && mx*(sii.size()-1)+1 == i) ans=i;
    }
    printf("%d\n",ans);
    return 0;
}