99클럽 코테 스터디 11일차 TIL + 프로그래머스 가장 많이 받은 선물문제 풀이

오늘의 문제

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

프로그래머스

 

문제 풀이

문제를 보고 기록해야 할 것을 아래와 같이 파악했다.

1. 한 사람이 다른 사람에게 준 선물 개수 & 받은 선물 개수
2. 한 사람의 선물 지수
3. 한 사람의 다음 달에 받을 선물 개수

 

아무래도 이름이 string이라 map을 사용하기로 결심했다.

‘한 사람이 다른 사람에게 준 선물 개수 & 받은 선물 개수’

이것은

1. 한 사람 이름
2. 다른 사람 이름
3. 준 선물 개수
4. 받은 선물 개수

이렇게 4개의 정보를 저장해야 했다.

그래서 아래와 같은 자료 구조가 나왔다.

map<string, map<string,pair<int,int>>> giveNtake;

 

생각해보면 중복이 있는데 이것보다 나은 자료구조가 떠오르지 않았다.

또 사용해보면 map을 2차원 배열처럼 map[준 사람][받은 사람] 이렇게 사용할 수 있어서 괜찮았다.

 

그리고 ‘한 사람의 선물 지수 & 한 사람의 다음 달에 받을 선물 개수’ 는

한 사람에 대한 정보라 역시 map을 사용하고 아래와 같은 자료 구조에 저장하였다.

map<string, pair<int,int>> data;

 

처음에는 그냥 vector 생각해서 추후에 정렬하기 쉽게 하기 위해 pair의 first에 다음 달에 받을 선물 개수를 넣었다.

그런데 map이 되면서 소용이 없어졌다.

 

이제 gifts를 돌면서 giveNtake map, data map에 값을 채웠다.

코드로는 아래와 같다.

    // gifts 정보로 map들 채우기
    for(int i=0;i<gifts.size();i++){
        string temp;
        stringstream stream;
        stream.str(gifts[i]);
        
        stream>>temp;
        string give = temp;
        
        stream>>temp;
        string take = temp;
        
        // 각각의 선물 지수 갱신
        data[give].second++;
        data[take].second--;
        
        // 각각의 주고 받은 선물 개수 갱신
        giveNtake[give][take].first++;
        giveNtake[take][give].second++;
    }

 

gifts의 정보는 stringstream을 통해 분리해냈다.

 

이제 giveNtake map을 돌며 다음 달 받을 선물 개수를 세면 된다.

처음에 초기화를 주고 받은 개수를 모두 (0, 0)으로 해 두었기 때문에 주고 받은 기록이 없어도 같은 선물 개수를 가진다.

 

한 사람이 다른 사람에게 준 선물 개수가 많다면 data map의 다음 달에 받을 선물 개수를 하나 늘렸다.

한 사람이 다른 사람에게 준 선물 개수가 같다면 (선물 개수 진짜 같거나 기록이 없는 경우) 각각의 선물 지수를 확인했다.

data map에서 선물 지수를 확인한 후 크다면 다음 달에 받을 선물 개수를 하나 늘렸다.

 

이때 map에서 양쪽에 기록이 되어 있어서 한쪽에 대해서만 큰지 확인하고 다음 달에 받을 선물 개수를 늘렸다.

    // giveNtake map 돌면서 다음 달 선물 받을 개수 세기
    for(int i=0;i<friends.size();i++){
        for(int j=0;j<friends.size();j++){
            string myName = friends[i];
            string friendName = friends[j];
            
            if(i!=j){
                int myPresent = giveNtake[myName][friendName].first;
                int friendPresent = giveNtake[myName][friendName].second;
                
                // 내가 준 선물이 더 많다면 다음 달 받을 선물 ++
                if(myPresent>friendPresent){
                    data[myName].first++;
                }
                // 주고 받은 선물 개수 같거나 || 주고 받은 기록 없다면 각각 선물 지수 확인
                else if(myPresent==friendPresent){
                    int myRate = data[myName].second;
                    int friendRate = data[friendName].second;
                    
                    // 내 선물 지숙 크다면 다음 달 받을 선물 ++
                    if(myRate>friendRate){
                        data[myName].first++;
                    }
                }
                
            }
        }   
    }

 

이제 마지막으로 data map에서 다음 달에 받을 선물 개수가 가장 큰 값을 찾으면 된다.

    // 다음 달 가장 많이 받는 선물 개수 찾기
    for(int i=0;i<friends.size();i++){
        int present = data[friends[i]].first;
        if(answer<present)
            answer=present;
    }

 

전체 코드

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

using namespace std;

/*
    선물 주고 받은 기록으로 다음 달에 누가 선물 많이 받을지 예측
    두 사람 선물 주고 받은 기록 있으면 더 많은 선물 준 사람이 다음 달에 그 사람에게서 하나 받음
    두 사람 선물 주고 받은 기록 없거나 같으면 선물 지수 더 큰 사람이 작은 사람에게서 하나 받음
    선물 지수 = 이번 달까지 자신이 친구들에게 준 선물 수 - 받은 선물 수 
    선물 지수도 같으면 다음 달에 선물 주고 받지 않음
    
    기록할 것
    선물 지수
    다음 달에 받을 선물 개수
    내가 누군가에게 준 것 & 받은 것  
*/

int solution(vector<string> friends, vector<string> gifts) {
    int answer = 0;
    
    map<string, map<string,pair<int,int>>> giveNtake;
    
    // 주고 받은 선물 저장 map 초기화
    for(int i=0;i<friends.size();i++){
        for(int j=0;j<friends.size();j++){
            if(i!=j){
                pair<int,int> t = make_pair(0,0);
                string friendName = friends[j];
                map<string,pair<int,int>> tMap;
                tMap[friendName] = t;
                giveNtake[friends[i]] = tMap;
            }
        }
    }
    
    // 받을 선물 개수, 선물 지수 벡터 초기화
    map<string, pair<int,int>> data;
    for(int i=0;i<friends.size();i++){
        pair<int,int> t = make_pair(0,0);
        string myName = friends[i];
        data[myName] = t;
    }
    
    // gifts 정보로 map들 채우기
    for(int i=0;i<gifts.size();i++){
        string temp;
        stringstream stream;
        stream.str(gifts[i]);
        
        stream>>temp;
        string give = temp;
        
        stream>>temp;
        string take = temp;
        
        data[give].second++;
        data[take].second--;
        
        giveNtake[give][take].first++;
        giveNtake[take][give].second++;
    }
    
    for(int i=0;i<friends.size();i++){
        for(int j=0;j<friends.size();j++){
            string myName = friends[i];
            string friendName = friends[j];
            
            if(i!=j){
                int myPresent = giveNtake[myName][friendName].first;
                int friendPresent = giveNtake[myName][friendName].second;
                
                if(myPresent>friendPresent){
                    data[myName].first++;
                }
                else if(myPresent==friendPresent){
                    int myRate = data[myName].second;
                    int friendRate = data[friendName].second;
                    
                    if(myRate>friendRate){
                        data[myName].first++;
                    }
                }
                
            }
        }   
    }
    
    
    for(int i=0;i<friends.size();i++){
        int present = data[friends[i]].first;
        if(answer<present)
            answer=present;
    }
    
    
    return answer;
}

 

 

회고

전체적으로 코드가 뭔가 깔끔하지 못하고 때려 박는 식으로 작성한 것 같다.

친구의 수가 50이 최대라 그냥 이런 식으로 해도 되었던 것 같다.

 

이중 map 사용하는 것과 양 쪽 다 기록하는 것을 좀 더 생각해보면 수정할 수 있을 것 같다.

하지만 지금은 잘 안 떠오르고 그냥 바로 떠오른 방법으로 풀어서 이렇게 된 것 같다.