[프로그래머스][2024 KAKAO WINTER INTERNSHIP] 가장 많이 받은 선물(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "가장 많이 받은 선물" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제는 친구들이 주고받은 선물 기록을 바탕으로, 다음 달에 가장 많은 선물을 받는 친구가 받을 선물의 수를 반환하는 문제입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크:

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

프로그래머스

문제 개요

이 문제는 친구들 사이에서 이루어진 선물 교환 기록을 분석하여, 다음 달에 누가 가장 많은 선물을 받게 될지를 예측하는 것입니다. 구체적으로, 친구들 간의 선물 교환 횟수를 기반으로 하여, 각 친구의 선물 지수를 계산하고, 이를 통해 다음 달에 누구에게 가장 많은 선물이 돌아갈지를 판단하는 문제입니다.

문제 해결 방법

이 문제를 해결하기 위해 다음과 같은 절차를 따릅니다:

1, 데이터 구조 설정:

친구들의 선물 교환 기록을 저장하기 위한 자료 구조를 설정합니다. 여기에는 각 친구가 준 선물의 수(gives), 받은 선물의 수(takes), 그리고 친구 간의 선물 교환 기록(friend_gift)이 포함됩니다.

2, 선물 교환 기록 분석:

주어진 gifts 배열을 순회하면서 각 친구가 얼마나 많은 선물을 주고받았는지를 분석합니다. 이를 통해 각 친구의 선물 지수를 계산할 수 있습니다.

3, 선물 지수 계산:

각 친구의 선물 지수는 그 친구가 준 선물의 수에서 받은 선물의 수를 뺀 값으로 계산됩니다(giftconst).

4, 다음 달 선물 받을 친구 예측:

친구들 간의 선물 교환 기록과 선물 지수를 바탕으로, 다음 달에 누가 가장 많은 선물을 받을지를 예측합니다. 이는 친구 간의 선물 교환 횟수와 선물 지수를 비교하여 결정됩니다.

코드 구현

이제 문제를 해결하기 위한 C++ 코드를 살펴보겠습니다. 코드는 주석을 통해 각 부분을 설명하였습니다.

#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

// 친구들 간 선물 교환 기록을 저장하는 벡터
vector<tuple<string, string, int>> friend_gift;
// 각 친구가 준 선물의 수를 기록하는 맵
map<string, int> gives;
// 각 친구가 받은 선물의 수를 기록하는 맵
map<string, int> takes;
// 각 친구의 선물 지수를 계산하는 맵
map<string, int> giftconst;

// 문자열을 특정 구분자로 나누는 함수
vector<string> Split(string input, string del) {
    vector<string> ret;
    int pos;
    string token;
    while ((pos = input.find(del)) != string::npos) {
        token = input.substr(0, pos);
        ret.push_back(token);
        input.erase(0, pos + del.size());
    }
    ret.push_back(input);
    return ret;
}

// 두 친구 간의 선물 교환 횟수를 반환하는 함수
int GetPre(string a, string b) {
    int count = 0;
    for (int i = 0; i < friend_gift.size(); i++) {
        if (a == get<0>(friend_gift[i]) && b == get<1>(friend_gift[i])) {
            count += get<2>(friend_gift[i]);
        }
    }
    return count;
}

// 선물을 준 횟수를 기록하는 함수
void AddGives(string giver) {
    gives[giver]++;
}

// 선물을 받은 횟수를 기록하는 함수
void AddTakes(string taker) {
    takes[taker]++;
}

// 친구들의 선물 교환 기록을 분석하고 다음 달에 선물을 가장 많이 받을 친구를 예측하는 함수
int solution(vector<string> friends, vector<string> gifts) {
    int answer = 0;

    // 선물 교환 기록 분석
    for (int i = 0; i < gifts.size(); i++) {
        vector<string> gift = Split(gifts[i], " ");
        tuple<string, string, int> temp = make_tuple(gift[0], gift[1], 1);
        friend_gift.push_back(temp);
        AddGives(gift[0]);
        AddTakes(gift[1]);
    }

    // 각 친구의 선물 지수 계산
    for (int i = 0; i < friends.size(); i++) {
        giftconst[friends[i]] = gives[friends[i]] - takes[friends[i]];
    }

    // 다음 달에 가장 많은 선물을 받을 친구를 예측
    map<string, int> count;
    for (int i = 0; i < friends.size(); i++) {
        for (int j = 0; j < friends.size(); j++) {
            if (friends[i] == friends[j]) continue;
            int checkI = GetPre(friends[i], friends[j]);
            int checkJ = GetPre(friends[j], friends[i]);
            if ((checkI == checkJ) || ((checkI == 0) && (checkJ == 0))) {
                if (giftconst[friends[i]] > giftconst[friends[j]]) {
                    count[friends[i]] += 1;
                }
            } else {
                if (checkI > checkJ) {
                    count[friends[i]] += 1;
                }
            }
        }
    }
    
    // 가장 많은 선물을 받을 것으로 예측되는 친구의 선물 수 계산
    for (int i = 0; i < friends.size(); i++) {
        if (answer < count[friends[i]]) {
            answer = count[friends[i]];
        }
    }
    
    return answer;
}

결과 및 시간 복잡도

주어진 예제에 대한 결과를 확인하면, 문제를 정확하게 해결하는 것을 확인할 수 있습니다. 이 알고리즘의 시간 복잡도는 입력으로 주어진 gifts 배열의 길이에 비례합니다. 따라서, 시간 복잡도는 O(N)이며, N은 gifts 배열의 길이입니다.