[Programmers] 가장 많이 받은 선물

프로그래머스

 

1. 문제 설명

 

2. 구현 아이디어 1 - 정답입니다!

주어진 정보대로 그대로 구현하면 되는 문제였다. 하지만, vector와 map 중 어느 자료구조를 사용할지 조금 망설이느라 문제를 푸는데 다소 시간이 소요되었다.

map이 생각보다 느린 자료구조이기 때문에 최대한 지양하려고 노력하고 있지만, 제한사항이 타이트하지 않아 map을 사용하였다.

소요 시간을 그나마 줄이기 위해 unordered_map을 사용하였다.

 

다음달에 가장 선물을 많이 받은 친구의 갯수를 출력할 때, map의 두번째 원소로 비교를 해주어야 하기 때문에 cmp라는 비교 함수를 만들어주고, cmp를 기준으로 비교하여 정렬하고 첫 번째 원소의 값을 반환하였다.

 

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

#include <iostream>

using namespace std;

bool cmp(pair<string, int> a, pair<string, int> b) {
    return a.second > b.second;
}

int solution(vector<string> friends, vector<string> gifts) {
    // 주고받은 선물 정보
    unordered_map<string, unordered_map<string, int>> friends_info;
    // 선물 지수
    unordered_map<string, int> gift_score;
    // 다음 달에 받은 선물
    unordered_map<string, int> next_gift;

    // 선물을 주고 받지 않는 경우에도 0으로 값 저장
    for (int i = 0; i < friends.size(); ++i) {
        for (int j = 0; j < friends.size(); ++j) {
            if (i == j) continue;

            friends_info[friends[i]][friends[j]] = 0;
            friends_info[friends[j]][friends[i]] = 0;
        }
    }

    // 공백을 기준으로 분리하여 unordered_map에 정보 저장
    for (int i = 0; i < gifts.size(); ++i) {
        stringstream ss(gifts[i]);
        string from, to;
        ss >> from >> to;

        // 주고받은 선물 정보
        friends_info[from][to] ++;

        // 선물 지수
        gift_score[from]++;
        gift_score[to]--;
    }

    for (int i = 0; i < friends.size(); ++i) {
        string from = friends[i];
        for (auto elem : friends_info[from]) {
            string to = elem.first;

            // 주고받은 선물이 없거나, 그 수가 같은 경우
            if (friends_info[from][to] == friends_info[to][from]) {
                if (gift_score[from] > gift_score[to]) next_gift[from]++;
            } else { // 주고받은 선물의 수가 다른 경우
                if (friends_info[from][to] > friends_info[to][from]) next_gift[from]++;
            }
        }
    }

    // 가장 선물을 많이 받는 사람 계산
    vector<pair<string, int>> ret(next_gift.begin(), next_gift.end());
    sort(ret.begin(), ret.end(), cmp);

    if (ret.empty()) return 0;

    return ret[0].second;
}