코테: 가장 많이 받은 선물

참고 코드

파트별로 역할을 나눌 필요가 있다.

1. 친구 이름을 인덱스로 매핑하여 효율적으로 데이터를 처리.
2. 선물 기록을 기반으로 선물 지수와 주고받은 횟수 업데이트.
3. 모든 친구 쌍을 비교하여 다음 달 받을 선물 수 계산.
4. 가장 많은 선물을 받을 친구가 받을 선물 수를 반환.

1. 친구 이름 매핑

unordered_map<string, int> friend_dict;
for (int i = 0; i < n; ++i) {
    friend_dict[friends[i]] = i;
}

friends 배열의 각 친구 이름을 순회하며, 이름을 키(key)로, 배열에서의 인덱스를 값(value)으로 저장.

예를 들어, friends = {"muzi", "ryan", "frodo", "neo"}라면 friend_dict는 다음과 같이 저장:

   friend_dict["muzi"] = 0;
   friend_dict["ryan"] = 1;
   friend_dict["frodo"] = 2;
   friend_dict["neo"] = 3;

2. 선물 기록 및 선물 지수 초기화

vector<vector<int>> table(n, vector<int>(n, 0));
vector<int> gift_indices(n, 0);

table[i][j]: 친구 i가 친구 j에게 준 선물 횟수. gift_indices[i]: 친구 i의 선물 지수(= 준 선물 수 - 받은 선물 수).

3. 선물 기록 분석

for (const string& gift : gifts) {
    size_t space = gift.find(' ');
    string giver = gift.substr(0, space);
    string receiver = gift.substr(space + 1);

    int giver_idx = friend_dict[giver];
    int receiver_idx = friend_dict[receiver];

    gift_indices[giver_idx]++;
    gift_indices[receiver_idx]--;
    table[giver_idx][receiver_idx]++;
}

1. gift.find(' ')로 문자열을 공백 기준으로 나눔.
   • giver: 선물을 준 사람.
   • receiver: 선물을 받은 사람.
2. friend_dict에서 주는 사람과 받는 사람의 인덱스를 가져옴.
3. gift_indices와 table을 업데이트:
   • gift_indices[giver_idx]++: 준 사람의 선물 지수 증가.
   • gift_indices[receiver_idx]--: 받은 사람의 선물 지수 감소.
   • table[giver_idx][receiver_idx]++: 준 사람과 받은 사람 간의 선물 기록 증가.

4. 다음 달 받을 선물 계산

vector<int> get_gift(n, 0);
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        if (i == j) continue;

        if (table[i][j] > table[j][i]) {
            get_gift[i]++;
        } else if (table[i][j] == table[j][i]) {
            if (gift_indices[i] > gift_indices[j]) {
                get_gift[i]++;
            }
        }
    }
}

1. 모든 친구 쌍을 비교 (i와 j):
   • 같은 친구는 비교 제외: if (i == j) continue;
2. 선물 조건에 따라 get_gift를 업데이트:
   • i가 j에게 더 많이 준 경우: get_gift[i]++.
   • 같은 횟수로 주고받은 경우:
     • i의 선물 지수(gift_indices[i])가 크면 get_gift[i]++.

5. 최대값 반환

return *max_element(get_gift.begin(), get_gift.end());

max_element 함수로 get_gift 배열에서 최대값 탐색. 이 값이 다음 달에 가장 많은 선물을 받는 친구가 받을 선물 수.