프로그래머스 2024 KAKAO WINTER INTERNSHIP 가장 많이 받은 선물(C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 2024 KAKAO WINTER INTERNSHIP - 가장 많이 받은 선물

---

문제 링크: 문제 보기

문제 설명:

친구들 사이에서 선물을 주고받은 기록이 주어질 때, 선물을 가장 많이 받은 친구의 점수를 계산합니다. 선물의 기록을 통해 누가 누구에게 선물을 주었는지 분석하고, 선물 횟수 및 우선순위에 따라 점수를 업데이트합니다.

---

문제 해결 코드

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

// 선물 주고받기 기록을 저장할 맵
map<pair<string, string>, int> mp1; // 친구 간 선물 횟수
map<string, int> mp2;                  // 각 친구가 받은 총 선물 수
map<string, int> ans;                  // 최종 점수 계산

int solution(vector<string> friends, vector<string> gifts) {
    int answer = 0;
    
    // 친구별 초기화
    for (const string& friend_name : friends) {
        mp2[friend_name] = 0;
        ans[friend_name] = 0;
    }
    
    // 모든 친구 쌍에 대해 초기화
    for (int i = 0; i < friends.size() - 1; i++) {
        for (int j = i + 1; j < friends.size(); j++) {
            string s1 = friends[i];
            string s2 = friends[j];
            mp1[{s1, s2}] = 0;
            mp1[{s2, s1}] = 0;
        }
    }
    
    // 선물 기록 처리
    for (const string& gift : gifts) {
        for (int j = 0; j < gift.size(); j++) {
            if (gift[j] == ' ') {
                string giver = gift.substr(0, j);
                string receiver = gift.substr(j + 1);
                mp1[{giver, receiver}]++;
                mp2[giver]++;
                mp2[receiver]--;
                break;
            }
        }
    }

    // 점수 계산
    for (int i = 0; i < friends.size() - 1; i++) {
        for (int j = i + 1; j < friends.size(); j++) {
            string s1 = friends[i];
            string s2 = friends[j];
            
            // 선물 횟수 비교
            if (mp1[{s1, s2}] > mp1[{s2, s1}]) {
                ans[s1]++;
                answer = max(answer, ans[s1]);
            } else if (mp1[{s1, s2}] < mp1[{s2, s1}]) {
                ans[s2]++;
                answer = max(answer, ans[s2]);
            } else {
                // 동일한 횟수라면 총 선물 수 비교
                if (mp2[s1] > mp2[s2]) {
                    ans[s1]++;
                    answer = max(answer, ans[s1]);
                } else if (mp2[s1] < mp2[s2]) {
                    ans[s2]++;
                    answer = max(answer, ans[s2]);
                }
            }
        }
    }
    
    return answer;
}

---

코드 설명

• 핵심 알고리즘: 주어진 친구 쌍의 선물 기록을 기반으로 점수를 계산합니다. 선물 횟수를 우선 비교하고, 동일한 횟수일 경우 총 선물 수로 우선순위를 결정합니다.
• 구현 세부사항:
• mp1: 친구 간의 선물 횟수를 기록합니다. 예를 들어, A가 B에게 선물을 준 경우 mp1[{A, B}]++가 이루어집니다.
• mp2: 각 친구가 받은 총 선물 수를 기록합니다. 선물을 준 사람은 +1, 받은 사람은 -1을 적용합니다.
• 모든 친구 쌍을 비교하며 점수를 계산합니다. 더 많은 선물을 받은 경우 점수를 증가시킵니다.
• 시간 복잡도 분석:
• 친구 쌍 초기화: O(n²), 여기서 n은 친구 수
• 선물 기록 처리: O(m), 여기서 m은 선물 기록 수
• 점수 계산: O(n²)
• 총 시간 복잡도: O(n² + m)

---

결과

이 코드는 선물 기록을 정확히 분석하여 점수를 계산하고, 가장 높은 점수를 반환합니다. 효율성과 구현의 단순함을 유지하며 동작합니다.

다른 접근 방식으로는 선물 기록을 그래프로 변환하여 탐색 알고리즘을 사용하는 방법이 있을 수 있습니다. 이 방법은 관계 분석을 더 직관적으로 수행할 수 있지만 구현이 복잡해질 수 있습니다.