프로그래머스 - 가장 많이 받은 선물

프로그래머스 가장 많이 받은 선물 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

여려 명의 친구들이 이번 달까지 선물을 주고받은 기록을 바탕으로 다음 달에 누가 선물을 많이 받을지 예측하려고 합니다.

• 두 사람이 선물을 주고받은 기록이 있다면 이번 달까지 두 사람 사이에 더 많은 선물을 준 사람한테 더 적게 선물을 준 사람이 다음 달에 선물을 하나 줍니다.
• 두 사람이 선물을 주고받은 기록이 하나도 없거나 주고받은 수가 같다면, 선물 지수가 더 큰 사람이 선물 지수가 더 작은 사람에게 선물을 하나 받습니다.
• 선물 지수는 이번 달까지 자신이 친구들에게 준 선물의 수에서 받은 선물의 수를 뺀 값입니다.
  이때, 다음달에 가장 많은 선물을 받는 친구가 받을 선물의 수를 구해야합니다.

문제 풀이

일단 친구들은 주어진 입력들이 string으로 되어 있기에 빠른 탐색을 위해 map컨테이너를 사용하여 이름들에 번호를 달아주었습니다.
그리고 배열로 친구들의 선물 지수와 두 사람들 간의 선물 이동을 기록해줍니다.

A와 B친구가 있을 경우 A친구가 선물을 받을 수 있는 경우는
1. A보다 B가 선물을 더 적게 줬을 경우
2. A와 B가 선물을 주고받은 수가 같을 때, A의 선물지수가 B보다 클 경우
나머지 경우는 선물을 받을 수 없습니다.
한 친구과 나머지 친구들을 전부 탐색하여 제일 선물을 많이 받은 사람의 선물 수를 출력하면 됩니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

vector<string> split(string input, char dlim)
{
	vector<string> result;

	stringstream ss;
	string stringBuffer;
	ss.str(input);
	
	while (getline(ss, stringBuffer, dlim))	
	{
		result.push_back(stringBuffer);
	}

	return result;
}

int solution(vector<string> friends, vector<string> gifts) {
    int answer = 0;
    unordered_map<string, int> friendDic;   //친구들을 번호로 매기기 위한 map
    vector<int> giftIndex(friends.size());  //친구들이 선물을 주고받은 수(선물지수)
    vector<vector<int>> giftRecord(friends.size(), vector<int>(friends.size(), 0)); //특정 친구에게 선물을 준 횟수
    
    for(int i = 0; i < friends.size(); i++)
    {
        friendDic.emplace(friends[i], i);
    }
    //선물을 준 상황을 배열에 입력
    for(string str : gifts)
    {
        vector<string> v = split(str, ' ');
        giftRecord[friendDic[v[0]]][friendDic[v[1]]]++;
        giftIndex[friendDic[v[0]]]++;
        giftIndex[friendDic[v[1]]]--;
    }
    
    int cnt;
    for(int i = 0; i < friends.size(); i++)
    {
        cnt = 0;
        for(int j = 0; j < friends.size(); j++)
        {
            if(i == j)  //자기 자신과는 계산X
                continue;
            if(giftRecord[i][j] > giftRecord[j][i]) //i 친구가 j 친구보다 선물을 더 많이 줬을 경우
            {
                cnt++;
            }else if(giftRecord[i][j] == giftRecord[j][i])  //i 친구와 j 친구의 선물 준 횟수가 같을 경우
            {
                if(giftIndex[i] > giftIndex[j]) //선물 지수가 더 클 경우
                {
                    cnt++;
                }
            }
        }
        answer = max(answer, cnt);  //제일 큰 값 저장
    }
    
    return answer;
}

출저

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