[C++] 프로그래머스 LV1. 가장 많이 받은 선물 (Kakao 기출문제)

 

허허.. LV1 이라고 해서 완전 얕봤다가 map을 까먹은 나는야 바보 천치라는 것을 깨닫게 해주었다..

물론 다른 방법이 많겠지만, 이게 가장 쉬운 접근법인것 같아 공유한다.

일단 다음달 선물을 계산하는 방법은 크게 다음과 같다.

• 주고 받은 선물 이력이 있는 경우 ➡️ 더 많이 준 사람에게 선물++
• 주고 받은 선물 이력이 없는 경우 ➡️ 선물 지수 비교 후, 선물 지수 큰 사람에게 선물++ (선물 지수도 같으면 0)

총 3개의 map을 이용했는데,

1. 주고받은 선물 확인용
2. 선물 지수 확인용
3. 다음 달에 받을 선물 개수 저장용

1번 map은 2차원으로 만들어 주었고 모든 gift를 돌면서 1번과 2번 map 값을 채워주었다.

만들어진 2차원 map(1번)을 다 검사하면 중복으로 검사가 되므로, 두번째 loop의 j는 i+1번째부터 시작하게끔하여 중복되지 않도록 검사했다.

각각의 검사를 통해 받을 선물을 더해주고, 최종적으로 가장 많이 선물을 받는 개수를 출력해주면 된다!

 

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

using namespace std;

int solution(vector<string> friends, vector<string> gifts) {
    int answer = 0;
    map<string, map<string, int> > giftExchange; //주고받은 선물 확인용
    map<string, int> giftScore; //선물지수용
    map<string, int> findMax; //다음달 선물 개수 저장용
    
    //위 세개의 map 초기화
    for(auto const& name : friends) {
        giftScore[name] = 0;
        findMax[name] = 0;
        for(auto const& name2 : friends) {
            giftExchange[name][name2] = 0;
        }
    }
    
    //주고받은 선물 기록 및 선물지수 계산
    for(auto const& gift : gifts) {
        stringstream ss(gift);
        string give, take;
        ss >> give >> take;
        giftExchange[give][take]++; //선물 준거 기록
        giftScore[give]++; //준건 +
        giftScore[take]--; //받은건 -
    }
    
    //전체 표의 반만(대각선) 검사
    for(int i=0; i<friends.size(); i++) {
        string name = friends[i];
        for(int j=i+1; j<friends.size(); j++) {
            string name2 = friends[j];
            if(name != name2) { //본인인 경우는 pass
                int one = giftExchange[name][name2];
                int two = giftExchange[name2][name];
                
                // 주고받은 선물 기록 대조
                if(one > two) findMax[name]++;
                else if(one < two) findMax[name2]++;
                else { //같다면 선물지수 대조
                    if(giftScore[name] > giftScore[name2]) findMax[name]++;
                    else{
                        if(giftScore[name] < giftScore[name2]) findMax[name2]++;
                    } //선물지수도 같으면 그냥 넘어감
                }
            }
        }
    }
    
    //다음달 받을 선물 중 max 찾기
    for(auto x : findMax) {
        answer = max(answer, x.second);
    }
    
    return answer;
}

 

 

하니까 쉬운데, 막상 문제 봤을때는 2차원 배열부터 시작해서 난리도 아니었다..

자료구조의 힘을 다시 깨닫는중..

왜 자꾸 잊어먹니..

복습만이 살길이다!