[ALGORITHM] LEVEL2 - 롤케이크 자르기

https://school.programmers.co.kr/learn/courses/30/lessons/132265

프로그래머스

과정

1. topping 안에 있는 숫자들의 개수를 chkb에 기록해준다.
2. 기록을 하면서 chkb가 0에서 바뀐 경우 새로운 숫자 이므로 b(동생이 먹을 개수)를 증가시킨다.
3. 다시 topping을 순회 하면서 이번엔 chkb에서 빼주고 chka에 더해준다.
4. 만약 chkb가 0이 된 경우 b를 감소시킨다.
5. chka가 0에서 변화한 경우 a를 증가시킨다.
6. a와 b가 동일하다는 것은 둘이 같은 맛의 개수를 먹는 것이므로 ans를 증가시킨다. 

주의할 점

배열의 최대 길이가 100만이므로 N^2번 탐색해서는 안된다.

값의 최대 사이즈도 1만 이므로 N*M (100만 * 1만)또한 안된다.

N으로 해결할 수 있는 방법을 찾자.

코드

#include <string>
#include <vector>

using namespace std;

int chka[10001], chkb[10001];
int N;
int a,b;

void init(vector<int> topping){
    fill(&chka[0],&chka[10001],0);
    fill(&chkb[0],&chkb[10001],0);
    
    a=b=0;
    N=topping.size();
    for(int i=0;i<N;++i){
        int num=topping[i];
        
        if(!chkb[num])
            ++b;
        ++chkb[num];
    }
}

int calc(vector<int> topping){
    int ans=0;
    
    for(int i=0;i<N;++i){
        int num=topping[i];
        
        --chkb[num];
        if(!chkb[num])
            --b;
        if(!chka[num])
            ++a;
        ++chka[num];
        
        if(a==b)
            ++ans;
    }
    
    return ans;
}

int solution(vector<int> topping) {
    int answer = -1;
    
    init(topping);
    answer=calc(topping);
    
    return answer;
}