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

가장 많이 받은 선물

문제 링크

가장 많이 받은 선물

분석

friends는 친구들의 이름 목록입니다.
gifts는 “A B”의 형태를 가진 문자열로, A가 B에게 선물을 준 기록을 나타냅니다.

두 친구에 대해, 다음 달에 누가 누구에세 선물을 하나 받을지 결정하는 규칙은 다음과 같습니다.

1. 이미 주고받은 기록이 있는 경우
   • 만약 A가 B에게 준 횟수가 더 많을 경우 B가 A에게 선물을 줍니다.
2. 주고받은 기록이 없거나 주고받은 횟수가 같은 경우
   • 선물 지수를 확인하여 더 낮은 사람이 높은 사람에게 선물을 줍니다.
   • 만약, 같은 경우 아무 선물 교환을 하지 않습니다.

예측을 위해 다음 정보를 저장해야 합니다.

• A가 B에게 선물을 준 횟수
• 각 친구가 선물을 준 횟수
• 각 친구가 선물을 받은 횟수

선물 지수는 선물은 준 수와 받은 수의 차를 통해 값을 구할 수 있기 때문에 값을 미리 구하거나 저장하지 않아도 됩니다.

풀이

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

int solution(vector<string> friends, vector<string> gifts) {
    int n = friends.size();
    
    // 이름을 인덱스로 매핑하기 위한 해시맵
    unordered_map<string, int> nameIndex;
    for (int i = 0; i < n; ++i)
    {
        nameIndex[friends[i]] = i;
    }
    
    // A가 B에게 준 선물 횟수
    vector<vector<int>> give(n, vector<int>(n, 0));

    // A가 지금까지 다른 사람들에게 준 선물 총합
    vector<int> givenCount(n, 0);

    // A가 지금까지 다른 사람들에게 받은 선물 총합
    vector<int> receivedCount(n, 0);
    
    // 선물 기록을 읽어서 데이터 갱신
    for (const auto& e : gifts)
    {
        // 물자열 공백 위치를 찾아 준 사람과 받은 사람을 구분한다.
        int spaceIndex = e.find(' ');
        
        string A = e.substr(0, spaceIndex);
        string B = e.substr(spaceIndex + 1);
        
        // 사람 이름으로 인덱스를 찾는다.
        int AIndex = nameIndex[A];
        int BIndex = nameIndex[B];
        
        ++give[AIndex][BIndex];     // A가 B에게 준 횟수 기록
        ++givenCount[AIndex];       // A가 준 선물 총합 +1
        ++receivedCount[BIndex];    // B가 받은 선물 총합 +1
    }
    
    // 다음 달에 i가 받을 선물 개수
    vector<int> nextReceived(n, 0);
    
    // 모든 친구 쌍에 대해 정해진 규칙에 따라 다음 달 선물을 예측한다.
    for (int i = 0; i < n; ++i)
    {
        for (int j = i + 1; j < n; ++j)
        {
            // i가 j보다 선물을 더 많이 준 경우
            if (give[i][j] > give[j][i])
            {
                ++nextReceived[i];
            }
            // j가 i보다 선물을 더 많이 준 경우
            else if (give[i][j] < give[j][i])
            {
                ++nextReceived[j];
            }
            // 주고받은 횟수가 같은 경우
            else
            {
                // 선물 지수 = 준 선물 수 - 받은 선물 수
                int AGiftScore = givenCount[i] - receivedCount[i];
                int BGiftScore = givenCount[j] - receivedCount[j];
                
                // 지수가 큰 쪽이 선물을 받는다.
                if (AGiftScore > BGiftScore)
                {
                    ++nextReceived[i];
                }
                else if (AGiftScore < BGiftScore)
                {
                    ++nextReceived[j];
                }
            }
        }
    }
    
    int answer = 0;
    
    // 다음 달에 받을 선물 개수 중 최대값을 찾는다.
    for (const auto& e : nextReceived)
    {
        if (answer < e)
        {
            answer = e;
        }
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n \times s + m \times l + n^2)$입니다.

• 해시맵을 초기화하는 반복문 $O(n \times s)$
  • s는 문자열 키의 해싱 비용입니다.
• 선물 기록을 통해 데이터를 갱신하는 반복문 $O(m \times l)$
  • l은 find와 substr을 수행하는 문자열의 길이입니다.
• 모든 친구 쌍을 탐색하는 반복문 $O(n^2)$
• 최댓값 탐색 $O(n)$
• $O(n \times s) + O(m \times l) + O(n^2) + O(n)$

공간 복잡도는 $O(n \times s + n^2)$입니다.

• 이름을 인덱스로 매핑하는 해시맵 $O(n \times s)$
  • s는 문자열의 길이입니다.
• A가 B에게 준 선물 횟수를 저장하는 2차원 배열 $O(n^2)$
• 준 선물, 받은 선물, 다음 달에 받을 선물 수를 저장한 일반 배열 $O(n)$
• $O(n \times s) + O(n^2) + O(n) + O(n) + O(n)$

테스트 성능

테스트 1 〉 통과 (0.02ms, 4.15MB)
테스트 2 〉 통과 (0.02ms, 3.64MB)
테스트 3 〉 통과 (0.03ms, 4.21MB)
테스트 4 〉 통과 (0.02ms, 4.14MB)
테스트 5 〉 통과 (0.23ms, 3.8MB)
테스트 6 〉 통과 (0.04ms, 4.43MB)
테스트 7 〉 통과 (0.12ms, 4.21MB)
테스트 8 〉 통과 (0.15ms, 4.19MB)
테스트 9 〉 통과 (0.60ms, 4.21MB)
테스트 10 〉 통과 (0.86ms, 4.17MB)
테스트 11 〉 통과 (0.53ms, 3.74MB)
테스트 12 〉 통과 (0.74ms, 4.21MB)
테스트 13 〉 통과 (1.56ms, 4.29MB)
테스트 14 〉 통과 (1.10ms, 4.36MB)
테스트 15 〉 통과 (1.06ms, 4.25MB)
테스트 16 〉 통과 (1.29ms, 4.53MB)
테스트 17 〉 통과 (0.03ms, 4.21MB)
테스트 18 〉 통과 (0.57ms, 4.21MB)
테스트 19 〉 통과 (1.05ms, 4.26MB)
테스트 20 〉 통과 (0.25ms, 4.13MB)