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

---

🔗 문제 링크

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

프로그래머스

---

👩‍💻 코드

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <iostream>

using namespace std;

int calculateGiftScore(const vector<vector<int>>& scores, int idx) {
    int row_sum = 0;
    int col_sum = 0;
    
    for (int k = 0; k < scores.size(); k++) {
        row_sum += scores[idx][k];
        col_sum += scores[k][idx];
    }
    
    return row_sum - col_sum;
}

int solution(vector<string> friends, vector<string> gifts) {
    int answer = 0;
    unordered_map<string, int> friends_index;
    vector<int> friends_receive(friends.size(), 0);
    vector<vector<int>> scores(friends.size(), vector<int>(friends.size(), 0));
    
    for(int i=0; i<friends.size(); i++){
        friends_index[friends[i]] = i;
    }
    
    for(const auto& gift : gifts){
        string give = gift.substr(0, gift.find(" "));
        string receive = gift.substr(gift.find(" ") + 1, gift.size());
        scores[friends_index[give]][friends_index[receive]] += 1;
    }
    
    for(int i=0; i<scores.size(); i++){
        for(int j=i+1; j<scores.size(); j++){
            if(scores[i][j] > scores[j][i]){
                friends_receive[i] += 1;
            }else if(scores[i][j] < scores[j][i]){
                friends_receive[j] += 1;
            }else{
                int i_gift_score = calculateGiftScore(scores, i);
                int j_gift_score = calculateGiftScore(scores, j);
                
                if (i_gift_score > j_gift_score) {
                    friends_receive[i] += 1;
                } else if (i_gift_score < j_gift_score) {
                    friends_receive[j] += 1;
                }
            }
        }
    }
    
    return *max_element(friends_receive.begin(), friends_receive.end());
}

---

📝 풀이

이름을 기준으로 index를 활용하기 위해 이름과 index를 한 쌍으로 저장한다 👉 friends_index

 

서로 주고 받은 선물 기록(gifts)를 반복하며 준 사람을 행, 받은 사람을 열로 치환한 후 선물 받은 횟수를 증가시킨다.

입출력 예시의 표처럼 score에 정보가 저장된다.

 

그 다음 반복문에서는 삼각형의 부분을 기준으로 비교하면 된다.

서로 주고 받은 횟수를 비교한 후 더 큰 경우 다음달에 선물을 받는 횟수(friends_receive)를 증가시킨다.

 

주고 받은 횟수가 같은 경우에는 선물 점수를 비교를 비교하는 로직이 필요하다.

calculateGiftScore 함수로 따로 작성하였다.
준 선물은 scores 행의 합이고 받은 선물은 scores 열의 합이다.

 

최종적으로 다음달에 받는 선물 횟수는 friends_receive에 저장된다.

friends_recieve의 최댓값을 return하면 답을 찾을 수 있다.