가장 많이 받은 선물

strcmp, strtok 안쓰고, c로 문자열 hash 푸는 습관 키우기

가장 많이 받은 선물

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>

// friends_len은 배열 friends의 길이입니다.
// gifts_len은 배열 gifts의 길이입니다.
// 파라미터로 주어지는 문자열은 const로 주어집니다. 변경하려면 문자열을 복사해서 사용하세요.
#define HASH_TABLE_SIZE 100
int hash_table[HASH_TABLE_SIZE];
int hash(const char *str)
{
    int hash = 0;
    while (*str) {
        hash = (hash * 31) + (*str++);
    }
    return hash;
}
void insert(int val)
{
    int idx = val % HASH_TABLE_SIZE;
    while (hash_table[idx] != -1) {
        idx++;
        idx %= HASH_TABLE_SIZE;
    }
    hash_table[idx] = val;
}
int search(const char *str)
{
    int val = hash(str);
    int idx = val % HASH_TABLE_SIZE;
    while (1) {
        if (hash_table[idx] == val)
            break;
        idx++;
        idx %= HASH_TABLE_SIZE;
    }
    return idx;
}

void get_gifts_hash_idx(const char *gift, int *idx1, int *idx2)
{        
    char f1[11] = { '\0', };
    char f2[11] = { '\0', };
    int len = strlen(gift), l = 0;
    char buf[16];
    for (int i=0;i<len;i++) {
        if (gift[i] == ' ') {
            buf[l++] = '\0';
            memcpy(f1, buf, l);
            l = 0;
            continue;
        }
        buf[l++] = gift[i];
    }
    buf[l++] = '\0';
    memcpy(f2, buf, l);
    
    *idx1 = search(f1);
    *idx2 = search(f2);
    
    return;
}

int gift_table[HASH_TABLE_SIZE][HASH_TABLE_SIZE];
int gift_factor[HASH_TABLE_SIZE];
int next_month_gift[HASH_TABLE_SIZE];

int solution(const char* friends[], size_t friends_len, const char* gifts[], size_t gifts_len) {
    int answer = 0;
    for (int i=0;i<HASH_TABLE_SIZE;i++) {
        hash_table[i] = -1;
        gift_factor[i] = 0;
        next_month_gift[i] = 0;
        for (int j=0;j<HASH_TABLE_SIZE;j++) 
            gift_table[i][j] = 0;
    }
    
    for (int i=0;i<friends_len;i++)
        insert(hash(friends[i]));
    
    for (int i=0;i<gifts_len;i++) {
        int idx1 = -1;
        int idx2 = -1;
        get_gifts_hash_idx(gifts[i], &idx1, &idx2);
        gift_table[idx1][idx2]++;
    }
    
    for (int i=0;i<HASH_TABLE_SIZE;i++) {
        if (hash_table[i] == -1)
            continue;
        int send_gift = 0;
        int receive_gift = 0;
        for (int j=0;j<HASH_TABLE_SIZE;j++) {
            if (i == j)
                continue;
            if (hash_table[j] == -1)
                continue;
            if (gift_table[i][j] == 0)
                continue;
            send_gift += gift_table[i][j];
            
            if (gift_table[j][i] == 0)
                continue;
            receive_gift += gift_table[j][i];
        }
        gift_factor[i] = send_gift - receive_gift;
    }
    
    for (int i=0;i<HASH_TABLE_SIZE;i++) {
        if (hash_table[i] == -1)
            continue;
        int from = i;
        for (int j=0;j<HASH_TABLE_SIZE;j++) {
            if (hash_table[j] == -1)
                continue;
            int to = j;
            if (from == to)
                continue;
            if (gift_table[from][to] == -1)
                continue;
            if (gift_table[from][to] > gift_table[to][from])
                next_month_gift[from]++;
            else if (gift_table[from][to] < gift_table[to][from])
                next_month_gift[to]++;
            else {
                if (gift_factor[from] > gift_factor[to])
                    next_month_gift[from]++;
                else if (gift_factor[from] < gift_factor[to])
                    next_month_gift[to]++;
            }
            gift_table[from][to] = -1;
            gift_table[to][from] = -1;
        }
    }
    
    for (int i=0;i<HASH_TABLE_SIZE;i++) {
        if (next_month_gift[i] == 0)
            continue;
        answer = next_month_gift[i] > answer ? next_month_gift[i] : answer;
    }
    
    return answer;
}