[해커랭크] Frequency Queries (C++)

문제 링크: www.hackerrank.com/challenges/frequency-queries/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps

Frequency Queries | HackerRank

 

1. 주의할 점

- X,Y,Z의 범위가 1~10^9사이다

- Map + 배열을 이용하여 해결한다

- 배열의 범위가 크지 않으므로, indexOutOfRange가 발생하지 않도록 예외처리를 한다

 

2. 구현

- Cnt[] 배열을 통해 i만큼의 숫자가 들어있는 수를 Cnt[i]에 표시한다(Ex. 2 2 3 3 3이 있다면, Cnt[2] =1, Cnt[3]=1)

- Map을 통해 <i 숫자, i 숫자가 있는 개수>를 표현한다

- Insert가 일어난 경우, Map에서 B의 개수 1 증가 + Cnt[] 배열 조정

- Delete가 일어난 경우, Map에서 B의 개수 1 감소 + Cnt[] 배열 조정

- 그 외의 경우, B가 Cnt[] 배열 범위를 벗어나거나, Cnt[B]값이 0이면 0을, 아니라면 1을 반환한다

int cnt[100001];        //횟수

// Complete the freqQuery function below.
vector<int> freqQuery(vector<vector<int>> queries) {
    vector<int> v;
    map<int, int> m;
    for(int i=0;i<queries.size();i++){
        int a = queries[i][0];
        int b = queries[i][1];
        if(a==1){       //insert
            if(m.find(b)!=m.end() && m[b]>0){ //기존에 B가 있던 경우
                int val = m[b];     //B가 Val만큼 존재
                cnt[val]--;
                cnt[val+1]++;
                m[b]++;
            }
            else{       //기존에 없던 경우
                m[b]=1;
                cnt[1]++;
            } 
        }
        else if(a==2){      //delete
            if(m.find(b)!=m.end() && m[b]>0){
                int val = m[b];     //B가 Val만큼 존재
                cnt[val]--;
                cnt[val-1]++;
                m[b]--;
            }
        }
        else{
            int val;
            (b>100000 || cnt[b]<=0) ? val=0 : val=1;
            v.push_back(val);
        }
    }
    return v;
}