프로그래머스 - 가장 많이 받은 선물 - C++

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

프로그래머스

 

#include <string>
#include <vector>
#include <map>
using namespace std;

// 1. 선물지수 알아내기
// 2. 선물을 더 많이준쪽이 하나 받음
// 3. 같거나 없다면 선물지수 많은쪽이 받음
// 4. 지수도 같다면 x

int solution(vector<string> friends, vector<string> gifts) {
    int answer = 0;
    // 준 수, 받은 수
    map<string, pair<int, int>> num;
    // 기준 이름, 기준이 선물준 이름, 줬는지여부, 몇개
    map<string, map<string, pair<bool, int>>> rela;

    for (int i = 0; i < friends.size(); i++)
    {
        num.insert({ friends[i],{0,0} });
        map<string, pair<bool, int>> c;
        for (int j = 0; j < friends.size(); j++)
        {
            if (friends[i] != friends[j])
                c.insert({ friends[j],{false,0} });
        }
        rela.insert({ friends[i],c });
    }

    for (int i = 0; i < gifts.size(); i++)
    {
        int idx = gifts[i].find(' ');
        string a = gifts[i].substr(0, idx);
        string b = gifts[i].substr(idx + 1);

        rela[a][b].first = true;
        rela[b][a].first = true;
        rela[a][b].second++;
        num[a].first++;
        num[b].second++;
    }
    int max = -1;
    for (int i = 0; i < friends.size(); i++)
    {
        int cnt = 0;
        int giftNum = num[friends[i]].first - num[friends[i]].second;
        for (int j = 0; j < friends.size(); j++)
        {
            if (friends[i] != friends[j])
            {
                // 선물교류가 있었다
                if (rela[friends[i]][friends[j]].first == true)
                {
                    // i 가 더 많이 줬다.
                    if (rela[friends[i]][friends[j]].second > rela[friends[j]][friends[i]].second)
                    {
                        cnt++;
                    }
                    else if (rela[friends[i]][friends[j]].second ==
                        rela[friends[j]][friends[i]].second)
                    {
                        int n1 = num[friends[j]].first - num[friends[j]].second;
                        if (giftNum > n1)
                            cnt++;
                    }
                }
                else
                {
                    int n1 = num[friends[j]].first - num[friends[j]].second;
                    if (giftNum > n1)
                        cnt++;
                }
            }
        }
        if (cnt > max)
            max = cnt;
    }

    return max;
}

이번 문제는 특정한 규칙에 의거해서 다음달 누가 선물을 가장 많이 받을지를 계산하는 문제이다.

 

friends에는 유저목록이, gifts에는 공백을 기준으로 선물준사람과 받는사람이 있다. 

map을 이용해서 num에는 유저가 선물을 준수와 받은 수를 종합적으로 나타냈고,

rela에는 한 유저가 모든유저와의 관계를 나타내며 교류한적이 있다면 ,true에 선물 준 수를 나타낸다. 

 

for (int i = 0; i < gifts.size(); i++)
    {
        int idx = gifts[i].find(' ');
        string a = gifts[i].substr(0, idx);
        string b = gifts[i].substr(idx + 1);

        rela[a][b].first = true;
        rela[b][a].first = true;
        rela[a][b].second++;
        num[a].first++;
        num[b].second++;
    }

gifts를 읽어서 데이터를 분석 및 저장하는 단계이다.

rela[a][b].first = true는 a유저가 b유저와의 관계에서 선물교류가 있었다 를 뜻한다.

rela[a][b].second는 a가 b에게 준 선물의 수이다.

num[a].first는 a유저가 준 선물의 개수이다.

num[b].second는 b유저가 받은 선물의 개수이다. 

 

선물지수는 준선물에서 받은선물을 빼야하기 때문에 필요하다.

 

for (int i = 0; i < friends.size(); i++)
    {
        int cnt = 0;
        int giftNum = num[friends[i]].first - num[friends[i]].second;
        for (int j = 0; j < friends.size(); j++)
        {
            if (friends[i] != friends[j])
            {
                // 선물교류가 있었다
                if (rela[friends[i]][friends[j]].first == true)
                {
                    // i 가 더 많이 줬다.
                    if (rela[friends[i]][friends[j]].second > rela[friends[j]][friends[i]].second)
                    {
                        cnt++;
                    }
                    else if (rela[friends[i]][friends[j]].second ==
                        rela[friends[j]][friends[i]].second)
                    {
                        int n1 = num[friends[j]].first - num[friends[j]].second;
                        if (giftNum > n1)
                            cnt++;
                    }
                }
                else
                {
                    int n1 = num[friends[j]].first - num[friends[j]].second;
                    if (giftNum > n1)
                        cnt++;
                }
            }
        }
        if (cnt > max)
            max = cnt;
    }

여기서 for문을 돌며 각 유저가 다음달에 얼마나 많이 받을지 계산하여 max값을 구한다. 

 

선물교류가 있었다면 누가 더 많은 선물을 줬는지, 또 그 개수가 같다면 누가 선물지수가 더 높은지를 판단하여 cnt를 증가시킨다. 

만약 교류가 없었다면 마찬가지로 선물지수가 누가 높은지를 판단하여 cnt를 증가시킨다.

for문에서 i 유저가 기준이다.