[프로그래머스] Lv.1 가장 많이 받은 선물 c++

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

프로그래머스

 

2024 KAKAO WINTER INTERNSHIP에 나온 문제입니다.

카카오톡의 선물하기 기능을 활용해 친구들에게 선물을 주고받은 기록을 바탕으로, 다음 달에 누가 가장 많은 선물을 받을지 예측하는 시스템을 개발하려 합니다.

1. 두 사람이 주고받은 선물 횟수를 비교하여, 더 많이 선물을 준 사람이 다음 달에 선물을 하나 받습니다.
   • 예: A가 B에게 선물을 5번 주고, B가 A에게 3번 줬다면, A가 다음 달에 선물을 받습니다.
2. 두 사람이 주고받은 기록이 없거나 횟수가 같다면, 선물 지수를 비교합니다.
   • 선물 지수는 자신이 준 선물 수에서 받은 선물 수를 뺀 값으로 계산됩니다.
   • 선물 지수가 높은 사람이 낮은 사람에게 선물을 하나 받습니다.
   • 선물 지수도 같다면 선물을 주고받지 않습니다.

예를 들어, 친구 목록이 ["muzi", "ryan", "frodo", "neo"]이고, 선물 기록이 ["muzi frodo", "muzi frodo", "ryan muzi", "ryan muzi", "frodo ryan"]인 경우, 위 규칙에 따라 다음 달에 가장 많은 선물을 받는 친구를 계산합니다.

 

풀이 방법

문자열을 파싱하고 데이터를 잘 정리하여 계산해주면 됩니다.

저는 3개의 구조를 선언했습니다.

 

• gift_summary: 각 친구가 지금까지 선물을 준 횟수와 받은 횟수를 저장하는 해시맵입니다.
  • 예: {"muzi": {준 선물 횟수, 받은 선물 횟수}}
• name_to_index: 친구 이름을 인덱스로 매핑하는 해시맵으로, 배열이나 행렬에 바로 접근 하기 위함입니다.
  • 예: {"muzi": 0, "ryan": 1}
• gift_matrix: 2차원 배열로, 누가 누구에게 몇 번 선물을 줬는지 구체적으로 기록합니다.
  • 예: gift_matrix[0][1]은 muzi가 ryan에게 준 선물 횟수입니다. 

이후 gifts 배열을 순회하며 각 선물을 준 사람과 받은 사람을 파싱하며 gift_summary와 gift_matrix를 업데이트 합니다.

• • gift_summary[giver].first++: 선물을 준 횟수 증가.
  • gift_summary[receiver].second++: 선물을 받은 횟수 증가.
  • gift_matrix[giver_index][receiver_index]++: 매트릭스에 기록.

계산된 gift_matrix를 이중for문으로 탐색하여 다음달 선물의 수를 각각 계산했습니다.

 

 

풀이 코드

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

using namespace std;

unordered_map<string,pair<int,int>> gift_summary;
unordered_map<string, int> name_to_index;
int gift_matrix[50][50];
string giver, receiver;
int giver_index, receiver_index;

int solution(vector<string> friends, vector<string> gifts) {
    vector<int> next_gift(friends.size());
    
    for(int i=0; i<friends.size(); i++) name_to_index[friends[i]] = i;
    for(string s : gifts){
        stringstream ss(s);
        ss >> giver >> receiver;
        
        giver_index = name_to_index[giver];
        receiver_index = name_to_index[receiver];
        
        gift_matrix[giver_index][receiver_index]++;
        gift_summary[giver].first++;
        gift_summary[receiver].second++;
    }
    
    for(int i=0; i<friends.size()-1; i++){
        for(int j=i+1; j<friends.size(); j++){
            if(gift_matrix[i][j]>gift_matrix[j][i]) next_gift[i]++;
            else if(gift_matrix[i][j]<gift_matrix[j][i]) next_gift[j]++;
            else{
                int gift1 = gift_summary[friends[i]].first-gift_summary[friends[i]].second;
                int gift2 = gift_summary[friends[j]].first-gift_summary[friends[j]].second;
                
                if(gift1 > gift2) next_gift[i]++;
                else if(gift1 < gift2) next_gift[j]++;
            }
        }
    }
    sort(next_gift.rbegin(), next_gift.rend());
    return next_gift[0];
}