[프로그래머스 / C언어] 가장 많이 받은 선물

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

프로그래머스

 

프로그래머스 코딩테스트 Lv.1 문제인 '가장 많이 받은 선물' 문제를 풀어보았다. 질문에는 Lv.1 문제가 아닌 것 같다는 말이 나오고 Lv.1 문제에서 정답률도 가장 낮을 정도로 복잡해 보이나, 사실 크게 복잡한 알고리즘이나 자료구조가 필요한 영역은 아니다.

문제를 풀 당시, 알고리즘 관련 대회를 준비 중에 있어 사소한 공간복잡도보다는 시간복잡도와 빠른 코드 작성에 초점을 맞춰 작성하였다. (malloc 사용 대신 제한된 최대 크기의 배열을 만든 점 등)

이 문제를 풀면서, sscanf나 calloc 함수의 존재를 알게 됐는데, 42에서 c언어를 주로 사용했다보니, 가장 low level의 함수만 사용하여 하나하나 손으로 구현하는 것에 익숙해져 있다보니 잊고 있었거나 존재조차 몰랐던 간편한 기능들을 가진 함수였다. calloc은 굳이 필요하지 않아 사용하지 않았지만, sscanf는 바로 활용해보았다. 

 

 

우선 "준사람 받은사람"의 형태로 작성된 gifts 배열을 순회하며, 준 사람과 받은 사람의 id를 찾는다. 여기서 id는 friends 배열에 해당 string이 위치한 인덱스이다. 이 지점에서 find_id 함수를 사용하게 되는데, 단순히 friends 배열을 순회하며 똑같은 string을 찾아 인덱스를 리턴하는 방식이다. 

그리고 record 배열 내, record[준사람의 id][받은사람의 id]의 위치에 1을 더해주어, '준사람'이 '받은사람'에게 선물을 준 개수를 세게 된다. 예를 들어, record[A][B]가 5라면 A가 B에게 선물을 5번 준 것이고, record[B][A]가 0이라면 B는 A에게 선물을 한 번도 주지 않은 것이다.

다음 willGet 배열을 만들어, 다음 달에 각 사용자가 받을 선물의 수를 센다. 문제에서 언급한대로, 내가 더 많이 선물을 준 경우에 한해서 다음달에 하나의 선물을 받게 되는데, 만약 똑같이 주고 받았을 경우, 선물 지수를 계산해야 한다. 이를 계산하기 위해서 get_index 함수를 사용한다.

마지막으로 willGet 배열에서 최대값을 찾아 리턴해주면 된다.

 

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

int find_id(const char* friends[], size_t friends_len, char* f) {
    for (int i = 0; i < friends_len; i++) {
        if (strcmp(friends[i], f) == 0) return i;
    }
    return -1;
}

int get_index(int record[50][50], int id, size_t friends_len) {
    int given = 0, gotten = 0;
    for (int i = 0; i < friends_len; i++) {
        if (id == i) continue;
        given += record[id][i];
        gotten += record[i][id];
    }
    return (given - gotten);
}

int solution(const char* friends[], size_t friends_len, const char* gifts[], size_t gifts_len) {
    int record[50][50] = {0};
    for (int i = 0; i < gifts_len; i++) {
        int len = strlen(gifts[i]);
        char* giving = (char*)malloc(sizeof(char) * len);
        char* gotten = (char*)malloc(sizeof(char) * len);
        sscanf(gifts[i], "%s %s", giving, gotten);
        record[find_id(friends, friends_len, giving)][find_id(friends, friends_len, gotten)]++;   
    }
    
    int willGet[50] = {0};
    for (int i = 0; i < friends_len; i++) {
        for (int j = i+1; j < friends_len; j++) {
            if (record[i][j] > record[j][i]) willGet[i]++;
            else if (record[i][j] < record[j][i]) willGet[j]++;
            else {
                int i_index = get_index(record, i, friends_len);
                int j_index = get_index(record, j, friends_len);
                if (i_index > j_index) willGet[i]++;
                else if (i_index < j_index) willGet[j]++;
            }
        }
    }
    
    int max = 0;
    for (int i = 0; i < friends_len; i++) {
        if (willGet[i] > max) max = willGet[i];
    }
    return max;
}