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

문제 링크

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

 

풀이

친구의 이름이 담긴 friends 벡터와 누가 누구에게 선물을 준 기록인 gifts 벡터가 주어진다.

 

3가지 단계를 거쳐 문제를 해결했다.

1. 입출력 예시와 같이 주고받은 선물 표를 구한다.

2. 선물 지수 표를 구한다.

3. 두 표를 사용해서 각 사람마다 받아야 하는 선물 개수를 계산해 최댓값을 구한다.

 

주고받은 선물 표는 아래와 같이 2차원 벡터로 만든다.

// 2차원 벡터 생성(presentTable)
int friend_size = friends.size(), gift_size = gifts.size();
vector<vector<int>> presentTable(friend_size, vector<int>(friend_size, 0));

string givef, getf;
for(int i = 0; i < gift_size; i++){
    // 선물을 준 사람과 받은 사람의 이름을 구한다.
    givef = gifts[i].substr(0, gifts[i].find(' '));
    getf = gifts[i].substr(gifts[i].find(' ')+1, gifts[i].length());
    
    // friends 벡터에서 각 이름이 몇번째인지 찾아 횟수를 기록한다.
    presentTable[find(friends.begin(), friends.end(), givef) - friends.begin()][find(friends.begin(), friends.end(), getf) - friends.begin()]++;
}

 

선물 지수 표는 (준 선물) - (받은 선물)을 계산하여 벡터로 만든다.

vector<int> presentN(friend_size);

int givep, getp;
for(int i = 0; i < friend_size; i++){
    givep = 0;
    getp = 0;
    // 준 선물의 개수
    for(int j : presentTable[i]){
    	givep += j;
    }
    // 받은 선물의 개수
    for(int j = 0; j < friend_size; j++){
        getp += presentTable[j][i];
    }
        
    presentN[i] = givep - getp;
}

 

presentTable 벡터를 사용해서 각 사람마다 선물을 받은 것보다 줬을 때가 더 많은 경우를 전부 찾습니다. 받은 것과 준 것의 횟수가 같은 경우에는 선물 지수를 고려하여 선물 개수를 계산합니다.

int total;
for(int i = 0; i < friend_size; i++){
    total = 0;
    
    // 각 사람마다 선물을 받게 되는 경우 계산
    for(int j = 0; j < friend_size; j++){
    	if((presentTable[i][j] > presentTable[j][i])
            || ((presentTable[i][j] == presentTable[j][i]) 
    	    && (presentN[i] > presentN[j]))){
    			total++;
    	} 
    }
    
    // 가장 많이 받는 경우를 찾는다
    if(total > answer) answer = total;
}

 

 

최종 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<string> friends, vector<string> gifts) {
    int answer = 0;
    
    int friend_size = friends.size();
    int gift_size = gifts.size();
    vector<vector<int>> presentTable(friend_size, vector<int>(friend_size, 0));
    vector<int> presentN(friend_size);
    
    string givef, getf;
    for(int i = 0; i < gift_size; i++){
        givef = gifts[i].substr(0, gifts[i].find(' '));
        getf = gifts[i].substr(gifts[i].find(' ')+1, gifts[i].length());
        
        presentTable[find(friends.begin(), friends.end(), givef) - friends.begin()][find(friends.begin(), friends.end(), getf) - friends.begin()]++;
    }
    
    int givep, getp;
    for(int i = 0; i < friend_size; i++){
        givep = 0;
        getp = 0;
        for(int j : presentTable[i]){
            givep += j;
        }
        for(int j = 0; j < friend_size; j++){
            getp += presentTable[j][i];
        }
        
        presentN[i] = givep - getp;
    }
    
    int total;
    for(int i = 0; i < friend_size; i++){
        total = 0;
        for(int j = 0; j < friend_size; j++){
            if((presentTable[i][j] > presentTable[j][i])
              || ((presentTable[i][j] == presentTable[j][i]) 
               && (presentN[i] > presentN[j]))){
                total++;
            } 
            else{
                
            }
        }
        if(total > answer) answer = total;
    }
    
    return answer;
}