[프로그래머스] 가장 많이 받은 선물 (C++)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/258712?language=cpp

아이디어1

string vector를 unordered_map을 이용해서 이름, 인덱스의 key, value로 변환해서 저장하기

• unordered_map은 해쉬맵이므로 빠름

unordered_map<string, int> indexMap;
int index = 0;
for (auto f : friends)
{
	indexMap.emplace(f, index);
	index++;
}

아이디어2

선물 주고 받은 수 매트릭스, 선물 지수 배열 만들기

<행렬, 배열 구하기>

vector<vector<int>> matrix(friends.size(),
                           vector<int>(friends.size(), 0));
vector<int> giftIndex(friends.size(), 0);
vector<int> giftCount(friends.size(), 0);

for (auto gift : gifts)
{
    int cur = gift.find(' ');
    string first = gift.substr(0, cur);
    string second = gift.substr(cur + 1, -1);
    int giver = indexMap.find(first)->second;
    int taker = indexMap.find(second)->second;

    matrix[giver][taker]++;
    giftIndex[giver]++;
    giftIndex[taker]--;
}

• string을 ' '기준으로 나눠 준 사람/받은 사람의 index를 구함
• 행렬[준 사람][받은 사람] 플러스
• 배열[준 사람] 플러스, 배열[받은 사람] 마이너스

<선물 받을 수 구하기>

for (int i = 0; i < friends.size(); ++i)
{
    for (int j = i + 1; j < friends.size(); ++j)
    {
        int diff = matrix[i][j] - matrix[j][i];
        if (diff > 0)
            giftCount[i]++;
        else if (diff < 0)
            giftCount[j]++;
        else
        {
            if (giftIndex[i] > giftIndex[j])
                giftCount[i]++;
            else if (giftIndex[i] < giftIndex[j])
                giftCount[j]++;
        }
    }
}

answer = *max_element(giftCount.begin(), giftCount.end());

• '선물 준 수 > 선물 받은 수'면 플러스
• 같으면 선물 지수가 높으면 플러스