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

프로그래머스

문제

 

이 문제는 다음달에 선물을 가장 많이 받는 사람의 선물 갯수를 구하는 문제이다.

 

다음달에 선물을 받는 조건

1. 이번 달에 본인이 상대방보다 선물을 많이 주었을 때
2. 이번 달에 선물을 주고 받은 갯수가 같고 선물 지수가 높을 때

선물을 준 갯수 - 선물을 받은 갯수 = 선물 지수

 

해당 문제는 맵을 사용하면 비교적 쉽게 해결할 수 있지만,

맵을 생각하지 못해 문제를 해결하지 못하고 블로그를 참고하여 풀이했습니다.

풀이

사람 별 번호를 맵에 저장하고 선물 지수와 선물 지표를 구한다.

각 사람 별로 다음 달에 받는 선물의 개수를 계산하고,

이를 내림차순으로 정렬한 후 0번째 선물 개수를 반환하는 방법으로 문제를 해결했다.

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

// https://codingjj.tistory.com/106#google_vignette 해당 블로그 참조해 풀이했습니다.
using namespace std;

map<string,int> giftNum; // 사람 별 선물지수 (사람, 선물지수)
map<string,int> personNum; // 사람 별 번호 (사람, 번호)
int giftGraph[50][50] = {0,}; // 선물 지표

void Init(vector<string> friends){ // 사람 별 번호 저장하는 함수
    int count = 0;
    
    for(string name : friends){
        personNum[name] = count;
        count ++;
    }
}
int cmp(int a, int b){
    return a>b;
}
int solution(vector<string> friends, vector<string> gifts) {
    Init(friends); 
    
    vector<int> result (50, 0); // 사람마다 다음달에 받아야할 선물 갯수가 들어가는 벡터
   
    for(string person : gifts){ // 선물 지수 및 선물 지표 
        istringstream iss(person); // 문자열 파싱
        string name1, name2;
        iss >> name1 >> name2; // 문자열 파싱
        
        giftNum[name1]++; // 선물을 준사람 선물 지수 ++
        giftNum[name2]--; // 선물을 받은 사람 선물 지수 --
        giftGraph[personNum[name1]][personNum[name2]] ++; // 선물 지표 ++        
    }
    
    for(int i = 0; i<friends.size(); i++){ // 다음달에 받아야할 선물 갯수 구하기
        for(int j= i; j<friends.size(); j++){
            // 이름 저장
            string name1 =  friends[i]; 
            string name2 =  friends[j];
            // 번호 저장    
            int num1 = personNum[name1];
            int num2 = personNum[name2];
            
            // 주고 받은 선물 갯수 비교
            if(giftGraph[num1][num2] > giftGraph[num2][num1])  result[num1] ++;
            else if(giftGraph[num1][num2] < giftGraph[num2][num1]) result[num2] ++;
            else{ // 주고 받은 선물 갯수가 같다면
                // 선물 지수 비교
                if(giftNum[name1] > giftNum[name2]) result[num1]++;
                else if(giftNum[name1] < giftNum[name2]) result[num2]++;
            }
            
        }
    }
    // 내림차순 정렬
    sort(result.begin(), result.end(), cmp);
    
    return result[0]; 
}

 

 

참고 블로그

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