[Hackerrank in C] frequency queries

문제

https://www.hackerrank.com/challenges/frequency-queries/problem?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps

Frequency Queries | HackerRank

 

풀이

원래는 int freq[10^9+1] = {0} 를 사용해 x,y,z가 나오는데로 frequency를 update하려고 했다.

근데 문제가 2개 있다.

1. int freq[1000000001] not allowed with stack/ static array limits. 

2. malloc을 사용한다 해도, to find typeC (if a specific frequency exists or not), need to go through 10^9 elements (maximum).

 

그래서 hashmap을 사용해 시간을 효율적으로 만들었다.

hashmap에서 key, value array (entries) 뿐만 아니라 freq array도 만들어 freq의 유무를 쉽게 확인할 수 있게 했다.

 

코드

typedef struct Entry {
    int key;
    int count; 
} Entry;

typedef struct Hashmap {
    Entry* entries;
    int size;
    int capacity;
    int* freq;
}Hashmap;

int hash(int key, int cap) {
    return (key%cap + cap)%cap;
}

Hashmap* createMap(int capacity) {
    Hashmap* map = (Hashmap*)malloc(sizeof(Hashmap));
    map->entries = (Entry*)calloc(capacity, sizeof(Entry));
    map->size = 0;
    map->capacity = capacity;
    map->freq = (int*)calloc(capacity, sizeof(int));
    return map;
}

void changefreq(Hashmap* map, int add_count, int sub_count) {
    if(sub_count > 0 && sub_count < map->capacity) map->freq[sub_count]--;
    if(add_count > 0 && add_count < map->capacity) map->freq[add_count]++;
    
}

void insert(Hashmap* map, int key) {
    int index = hash(key, map->capacity);
    int size = 0;
    
    while(map->entries[index].key != 0 && map->entries[index].key != key && size < map->capacity) {
        index = (index+1) % map->capacity;
        size++;
    }
    
    if(map->entries[index].key == 0) {
        map->entries[index].key = key;
        map->size++;
    }
    map->entries[index].count++;
    changefreq(map, map->entries[index].count, map->entries[index].count-1);
}

int getCount(Hashmap* map, int key) { // NOT USED
    int index = hash(key, map->capacity);
    while(map->entries[index].key != 0) {
        if(map->entries[index].key == key) return map->entries[index].count;
        index = (index+1) % map->capacity;
    }
    return 0;
}

int isfrequency(Hashmap* map, int count) {
    if(count > 0 && count < map->capacity && map->freq[count] > 0) return 1;
    return 0;
}

void deleteOne(Hashmap* map, int key) {
    int index = hash(key, map->capacity);
    while(map->entries[index].key != 0 && map->entries[index].key != key) {
        index = (index+1) % map->capacity;
    }
    if(map->entries[index].key != key) return;
    if(map->entries[index].count == 1) {
        map->entries[index].key = 0;
        map->size--;
    }
    
    changefreq(map, map->entries[index].count-1, map->entries[index].count);
    map->entries[index].count--;

    
}
int* freqQuery(int queries_rows, int queries_columns, int** queries, int* result_count) {
    // int freq[1000000000] = {0};  -> not a good idea, use hashmap
    Hashmap* hashmap = createMap(100001); // max q value
    
    int* result  = (int*)malloc(queries_rows * sizeof(int));
    *(result_count) = 0;
    int idx = 0;
    
    for(int i=0; i<queries_rows; i++) {
        int a = queries[i][0];
        int b = queries[i][1];
        if(a == 1) insert(hashmap, b);
        else if(a == 2) deleteOne(hashmap, b);
        else if(a == 3) {
            if(isfrequency(hashmap, b) > 0) {
                result[(idx)++] = 1;
                printf("1\n");
            } else {
                 result[(idx)++] = 0;
                 printf("0\n");
            }
        }
    }
    printf("%d\n", idx);
    *result_count = idx;
    return result;
}