(프로그래머스 c++ KAKAO) 가장 많이 받은 선물

https://school.programmers.co.kr/learn/courses/30/lessons/258712?language=cpp

프로그래머스

 

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

using namespace std;

int solution(vector<string> friends, vector<string> gifts) {
    int answer = 0;
    map<string, map<string, int>> history; // giver : (taker, count)
    map<string, pair<int, int>> score; // name : (give, take)
    
    // initialize the history map and score map
    for (auto i = 0; i < friends.size(); i++) {
        for (auto j = 0; j < friends.size(); j++) {
            if (friends[i] != friends[j]) {
                history[friends[i]][friends[j]] = 0;
                
                if (score.find(friends[i]) == score.end()) {
                    score[friends[i]] = make_pair(0, 0);
                }
                
                if (score.find(friends[j]) == score.end()) {
                    score[friends[j]] = make_pair(0, 0);
                }
            }
        }
    }
    
    // check
    for (auto gift : gifts) {
        istringstream iss(gift);
        string giver;
        string taker;
        
        iss >> giver >> taker;
        ++history[giver][taker];
        ++score[giver].first;
        ++score[taker].second;
    }
    
    for (auto giver : history) {
        int current_gift_count = 0;
        auto giver_name = giver.first;
        
        for (auto taker : giver.second) {
            auto taker_name = taker.first;
            auto give_count = taker.second;
            auto take_count = history[taker_name][giver_name];
            
            if (give_count == take_count) {
                auto giver_gift_score = score[giver_name].first - score[giver_name].second;
                auto taker_gift_score = score[taker_name].first - score[taker_name].second;
                
                if (giver_gift_score > taker_gift_score) {
                    ++current_gift_count;
                }
            } else if (give_count > take_count) {
                ++current_gift_count;
            }
        }
        
        answer = answer < current_gift_count ? current_gift_count : answer;
    }
    
    return answer;
}

 

맵을 주로 이용해서 푼 문제.

카카오 문제는 지문이 가장 어려운 것 같다...

 

우선 2개의 맵을 이용했다.

선물을 주고 받은 횟수를 저장하기 위한 맵인 history.

각자의 주고 받은 선물 횟수를 저장하는 맵인 score.

 

history맵의 형식은 value를 map으로 해서 이름으로 선물을 준 횟수를 쉽게 얻어내기 위해 아래처럼 만들었다.

선물을 준 사람(key) : {선물을 받은 사람(key), 선물을 준 횟수(value)}(map)

 

score맵은 각자 자신이 다른 사람들에게 선물을 주거나 받은 횟수를 저장한다.

선물을 준 사람(key) : {선물을 준 횟수, 선물을 받은 횟수}(pair)

 

1. Initialize the maps

// initialize the history map and score map
    for (auto i = 0; i < friends.size(); i++) {
        for (auto j = 0; j < friends.size(); j++) {
            if (friends[i] != friends[j]) {
                history[friends[i]][friends[j]] = 0;
                
                if (score.find(friends[i]) == score.end()) {
                    score[friends[i]] = make_pair(0, 0);
                }
                
                if (score.find(friends[j]) == score.end()) {
                    score[friends[j]] = make_pair(0, 0);
                }
            }
        }
    }

 

우선 맵을 모두 초기화한다.

check하는 로직에서 해도 되지만, 알아보기 쉽게 initialize를 먼저 했다.

history맵은 자신을 제외한 다른 사람들의 이름과 횟수인 0을 넣어주었다.

score맵도 선물을 준 사람과 받은 사람의 이름을 key로 하여 모두 0으로 초기화했다.

 

2. Check the gifts vector

// check
    for (auto gift : gifts) {
        istringstream iss(gift);
        string giver;
        string taker;
        
        iss >> giver >> taker;
        ++history[giver][taker];
        ++score[giver].first;
        ++score[taker].second;
    }

initializing을 했으니, gifts 를 순회하면서 각 맵에 넣어주면 된다.

istringstream을 이용해서 띄어쓰기를 delimeter로 giver와 taker를 구분한다.

history 맵은 giver를 key로 하여 taker value(map)에 접근해서 선물을 준 횟수(second map value)를 증가시켜준다.

 

score맵도 업데이트를 한다.

giver의 first = 선물을 준 횟수,

taker의 second = 선물을 받은 횟수를 뜻하기 때문에 각각을 + 1 해준다.

 

3. Calculate

// Calculate
    for (auto giver : history) {
        int current_gift_count = 0;
        auto giver_name = giver.first;
        
        for (auto taker : giver.second) {
            auto taker_name = taker.first;
            auto give_count = taker.second;
            auto take_count = history[taker_name][giver_name];
            
            if (give_count == take_count) {
                auto giver_gift_score = score[giver_name].first - score[giver_name].second;
                auto taker_gift_score = score[taker_name].first - score[taker_name].second;
                
                if (giver_gift_score > taker_gift_score) {
                    ++current_gift_count;
                }
            } else if (give_count > take_count) {
                ++current_gift_count;
            }
        }
        
        answer = answer < current_gift_count ? current_gift_count : answer;
    }
    
    return answer;

시간이 가장 많이 들어갔던 부분.

변수 네이밍을 잘 정해서 헷갈리지 않도록 해야한다.

history맵을 순회하면서 모든 조건을 확인해준다.

2중 map이기 때문에 first, second 멤버 변수가 많이 쓰인다.

그래서 헷갈리지 않기 giver, taker, count... 등등을 사용했다.

또한, 선물 횟수의 최대값을 구하기 위해 임시 변수인 current_gift_count를 이용해서 asnwer와 비교해서 값을 업데이트 한다.

 

가장 까다로운 조건부터 검사한다.

1. 누군가에게 선물을 준 횟수와, 누군가로부터 선물을 받은 횟수가 같은 경우

처음 history맵의 선물을 준 횟수를 0으로 초기화했기 때문에, 서로가 선물을 주고받지 않았으면 0이다.

그렇기 때문에 카운팅을 하지 않았으므로 두 수가 같다.

 

이 조건에 해당하는 경우, 선물 지수를 비교하면 된다.

score에서 선물을 준 사람의 선물 지수와 선물을 받은 사람의 선물 지수를 비교해서,

선물을 준 사람의 지수가 큰 경우 current_gift_count를 +1 해준다.

 

2. 선물을 주고 받은 횟수 비교

이 조건은 쉽다.

선물을 주고받은 이력이 있는 경우, 서로의 선물 주고받은 횟수를 비교해서 더 큰 사람이 받으면 된다.

 

Last

한 사람의 history를 모두 순회했다면, answer를 업데이트 할지말지 결정하면 된다.

current_gift_count와 answer를 비교해서 더 큰 값으로 업데이트한다.

 

그리고 return 하면 끝.

 

테스트 1 〉	통과 (0.05ms, 4.21MB)
테스트 2 〉	통과 (0.06ms, 4.15MB)
테스트 3 〉	통과 (0.12ms, 4.2MB)
테스트 4 〉	통과 (0.15ms, 4.13MB)
테스트 5 〉	통과 (1.01ms, 4.2MB)
테스트 6 〉	통과 (0.25ms, 4.21MB)
테스트 7 〉	통과 (1.03ms, 3.77MB)
테스트 8 〉	통과 (0.87ms, 4.15MB)
테스트 9 〉	통과 (3.04ms, 3.75MB)
테스트 10 〉	통과 (4.21ms, 4.02MB)
테스트 11 〉	통과 (3.36ms, 4.21MB)
테스트 12 〉	통과 (3.24ms, 3.92MB)
테스트 13 〉	통과 (7.65ms, 4.24MB)
테스트 14 〉	통과 (6.49ms, 4.17MB)
테스트 15 〉	통과 (9.64ms, 4.17MB)
테스트 16 〉	통과 (9.02ms, 4.7MB)
테스트 17 〉	통과 (0.13ms, 4.22MB)
테스트 18 〉	통과 (3.01ms, 4.23MB)
테스트 19 〉	통과 (7.87ms, 4.24MB)
테스트 20 〉	통과 (3.16ms, 4.2MB)

 

** chat gpt로 문제 풀이를 했을 때는, 엄청 빠른 결과를 얻을 수 있다. 2승 1패다.