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

프로그래머스

 

 

이름을 인덱스로 매핑하기 위한 Map

서로 주고 받은 선물 개수를 저장하는 2차원 배열

각자 선물 지수를 저장하는 1차원 배열

 

위 3가지를 이용해서 문제를 해결

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

using namespace std;

int giftArray[50][50]; 		//주고 받은 선물 배열
int indexToGiftFactor[50];	//선물 지수 배열

map<string, int> nameToIndex;	//이름을 인덱스로 매핑

int solution(vector<string> friends, vector<string> gifts) {
    int answer = 0;
    
    for(int i = 0; i < friends.size(); i++) //우선 friends의 이름들을 순서대로 인덱스와 매핑
        nameToIndex[friends[i]] = i;
    
    for(int i = 0; i < gifts.size(); i++){
        istringstream iss(gifts[i]);
        string name1, name2;
        iss >> name1 >> name2;		
        
        int idx1 = nameToIndex[name1]; //idx1 = 주는 사람
        int idx2 = nameToIndex[name2]; //idx2 = 받는 사람
        
        indexToGiftFactor[idx1]++;	//주는 사람의 선물 지수 증가
        indexToGiftFactor[idx2]--;	//받는 사람의 선물 지수 감소
        giftArray[idx1][idx2]++;	//idx1이 idx2한테 준 선물 갯수 증가
    }
    
    for(int i = 0; i < friends.size(); i++){
        int giftCount = 0;
        string name1 = friends[i];
        int idx1 = nameToIndex[name1];	//idx1 = 주는 사람
        
        for(int j = 0; j < friends.size(); j++){
            if(i == j) continue;
                
            string name2 = friends[j];
            int idx2 = nameToIndex[name2];	//idx2 = 받는 사람
            
            if(giftArray[idx1][idx2] > giftArray[idx2][idx1] || 
               (giftArray[idx1][idx2] == giftArray[idx2][idx1] && indexToGiftFactor[idx1] > indexToGiftFactor[idx2]))
               giftCount++;	//idx1이 idx2에게 준 선물의 개수가 많거나 같으면서 선물지수가 높으면 받는 선물의 개수 증가 
        }
        
        if(giftCount > answer) answer = giftCount; //받는 선물 개수가 answer보다 크면 갱신
    }
    
    return answer;
}