프로그래머스 <2024 KAKAO WINTER INTERNSHIP> 258712: 가장 많이 받은 선물

문제 요약

당신의 친구들이 이번 달까지 선물을 주고받은 기록을 바탕으로 다음 달에 누가 선물을 많이 받을지 예측하려고 합니다.

• 두 사람이 선물을 주고받은 기록이 있다면, 이번 달까지 두 사람 사이에 더 많은 선물을 준 사람이 다음 달에 선물을 하나 받습니다.
• 두 사람이 선물을 주고받은 기록이 하나도 없거나 주고받은 수가 같다면, 선물 지수가 더 큰 사람이 선물 지수가 더 작은 사람에게 선물을 하나 받습니다.
  • 선물 지수는 이번 달까지 자신이 친구들에게 준 선물의 수에서 받은 선물의 수를 뺀 값입니다.
    
• 만약 두 사람의 선물 지수도 같다면 다음 달에 선물을 주고받지 않습니다.
  
  위에서 설명한 규칙대로 다음 달에 선물을 주고받을 때, 당신은 선물을 가장 많이 받을 친구가 받을 선물의 수를 알고 싶습니다.

문제 분류

• 해시
• 문자열

문제 풀이

이 문제는 총 세가지.
1. 누가 누구에게 몇 개의 선물을 주었는가.
2. 누구는 총 몇 개의 선물을 주었는가.
3. 누구는 총 몇 개의 선물을 받았는가.
에 대해 정확하게 답변이 가능하면 문제를 쉽게 풀 수 있다.

우선 1번, 입력의 값이 모두 문자열이므로 일반적인 배열로는 풀 수 없다. 따라서 map으로 구현하였는데, 키는 string, 그 값을 multiset<string>으로 주었다.
우선 주어지는 gifts를 차례로 순차하며, 탐색하는 문자열을 띄어쓰기를 기준으로 분할한다. 이렇게 얻은 a와 b의 문자열에 대해, a는 준 사람의 이름, b는 받은 사람의 이름이다.
이제 a가 b에게 선물을 한 개 주었다는 것을 표현해야 하는데, multiset<string>을 값으로 주면 편리하다. 키는 a이고 값은 a가 준 선물을 받은 사람의 이름들이다. a에게 선물을 받은 b를 a의 multiset에 insert()하여 그것을 표현한다.

즉, a가b에게 몇 개의 선물을 주었는가는 m.find(a)->second.count(b)로 표현 가능하다.

2번과 3번은 단순히 두 개의 set<string>으로 해결했다. s1은 준 사람의 이름들, s2는 받은 사람의 이름들이다. gifts의 탐색 중 모두 insert()하였고, 종료되면 set의 count()로 개수를 파악하여 val[i]에 i번째 사람의 선물 지수를 구해주었다.

이제 끝이다. v 벡터는 i번째 사람이 몇 개의 선물을 받는지 카운트한 것이다. 서로 다른 사람 i와 j에 대해서, i가 j에게 준 선물의 개수(l), j가 i에게 준 선물의 개수(r)를 구한 뒤, l > r이라면 v[i]++, l < r이라면 v[j]++, 둘이 같다면 선물 지수로 파악하여 알맞은 곳에 v[]++를 표시한다.

끝으로, *max_element()로 v의 최댓값을 구하여 반환하면 된다.

풀이 코드

#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

int solution(vector<string> friends, vector<string> gifts) {
    int answer = 0;
    map<string, multiset<string>> m;
    multiset<string> s1, s2; // 준 것 받은 것 카운트 위함
    int val[50];
    vector<int> v(50);
    string a, b;
    
    for(int i = 0; i < gifts.size(); i++) {
        // 문자열 분할
        for(int j = 0; j < gifts[i].length(); j++) {
            if(gifts[i][j] == ' ') {
                a = gifts[i].substr(0, j);
                b = gifts[i].substr(j + 1);
            }
        }
        auto t = m.find(a);
        if(t == m.end()) {
            t = m.insert({a, multiset<string>()}).first;
        }
        t->second.insert(b);
        s1.insert(a);
        s2.insert(b);
    }
    for(int i = 0; i < friends.size(); i++) {
        val[i] = s1.count(friends[i]) - s2.count(friends[i]);
    }
    for(int i = 0; i < friends.size(); i++) {
        auto t = m.find(friends[i]);
        for(int j = i + 1; j < friends.size(); j++) {
            auto t2 = m.find(friends[j]);
            int l = 0, r = 0;
            if(t != m.end()) l = t->second.count(friends[j]);
            if(t2 != m.end()) r = t2->second.count(friends[i]);
            if(l > r)
                v[i]++;
            else if(l < r)
                v[j]++;
            else {
                if(val[i] < val[j])
                    v[j]++;
                else if(val[i] > val[j])
                    v[i]++;
            }
        }
    }
    answer = *max_element(v.begin(), v.end());
    
    return answer;
}