[코딩테스트] [프로그래머스] 가장 많이 받은 선물

문제

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

---

풀이

1. map<string, int>로 사람 이름별 인덱스를 저장한다.

2. 이중벡터 giftCount를 만들어 giftCount[i][j] = i가 j에게 준 선물 갯수 를 저장한다.

3. 벡터 giftDiff를 만들어 선물 지수를 저장한다.

4. giftCount를 순회하며 i가 j에게 준 선물 개수와 j가 i에게 준 선물 개수를 비교하고, 더 큰 쪽의 다음달 선물 개수를 증가시킨다.
   4-1. 만약 주고받은 선물이 없거나, 개수가 같을 경우 선물 지수를 비교하여 더 큰 쪽의 다음달 선물 개수를 증가시킨다.

5. 다음달 선물 개수 벡터를 순회하며 가장 큰 값을 반환한다.

---

코드

#include <string>
#include <vector> 
#include <map> 
#include <sstream>

using namespace std;

int solution(vector<string> friends, vector<string> gifts) 
{
    map<string, int> stringToIndex;
    for(int i=0; i<friends.size(); i++)
    {
        stringToIndex.insert({friends[i], i});
    }
    
    vector<vector<int>> giftCount(friends.size(), vector<int>(friends.size(), 0)); 
    vector<int> giftDiff(friends.size(), 0);
    for (string s : gifts)
    {
        stringstream ss(s);
        string giver, receiver;
        ss >> giver >> receiver;
        
        giftCount[stringToIndex[giver]][stringToIndex[receiver]]++;
        
        giftDiff[stringToIndex[giver]]++;
        giftDiff[stringToIndex[receiver]]--;
    }

    vector<int> nextMonth(friends.size(), 0);
    for (int i=0; i<giftCount.size() - 1; i++)
    {
        for(int j=i+1; j<giftCount[0].size(); j++)
        {
            if (giftCount[i][j] > giftCount[j][i])
            {
                nextMonth[i]++;
            }
            else if(giftCount[i][j] < giftCount[j][i])
            {
                nextMonth[j]++;
            }
            else
            {
                if(giftDiff[i] > giftDiff[j])
                    nextMonth[i]++;
                else if(giftDiff[i] < giftDiff[j])
                    nextMonth[j]++;
            }
        }
    }
    
    int result =0;
    for(int i : nextMonth)
    {
        result = max(result, i);
    }
    
    return result;
}

---

다른 풀이와 코드

0. 서로에게 준 선물 개수 벡터 순회를 깔끔하게 한 것 같아서 참고

#include <string>
#include <vector>
#include <map>
#include <sstream>

using namespace std;

int solution(vector<string> friends, vector<string> gifts) {

    vector<int> point(friends.size(), 0);
    vector<vector<int>> count(friends.size(), vector<int>(friends.size(), 0));
    map<string, int> m;

    for(int i=0;i< friends.size(); i++) 
        m.insert({friends[i], i});

    for(int i = 0; i < gifts.size(); i++) {
        string from, to;
        stringstream parse(gifts[i]);
        parse >> from >> to;

        int fromIdx = m[from], toIdx = m[to];
        count[fromIdx][toIdx]++;

        point[fromIdx]++;
        point[toIdx]--;
    }

    int ans = 0;

    for(int i = 0; i < friends.size(); i++) {
        int res = 0;

        for(int j = 0; j < friends.size(); j++) {
            if(i == j || count[i][j] < count[j][i]) continue;

            if(count[i][j] > count[j][i]) res++;
            else {
                if(point[i] > point[j]) res++;
            }
        }

        ans = max(res, ans);
    }

    return ans;
}