[프로그래머스/C++] 가장 많이 받은 선물 (2024 KAKAO WINTER INTERNSHIP)

 

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

문제 자체는 어려운 문제가 아니다. 단순히 +1로 더해가면서 구분만 하면 되는 문제기 때문이다.

 

대신 효율적인 코드를 위해 map과 split을 구현하는게 약간 어려울 수 있다.

 

map을 사용해 친구들을 key value값으로 빠르게 2차원 vector에서 찾을 수 있도록 변환했고, split 함수를 구현해 누가 누구에게 선물을 줬는지 빠르게 파악하도록 했다.

 

A가 B에게 선물을 주면 2차원 vector의 [A][B]에+1, [B][A]에 -1, 그리고 선물 지수의 A의 값을 +1, B의 값을 -1 하면 된다.

 

최종적으로 누가 선물을 가장 많이 받는지 비교를 위해 2차원 vector와 선물지수를 비교하며 계산하면 된다.

​

[아이디어 정리]

1. map으로 친구의 이름과 index를 매칭해 index의 접근을 빠르게 한다.​
2. 2차원 vector에 누가 누구에게 선물을 줬는지 기록하고, 1차원 vector에 선물지수를 기록한다.
3. 비교 결과 가장 선물을 많이 받을 때, 몇개를 받는지 return 한다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <map>
#include <sstream>
using namespace std;

map<string, int> FM;
vector<vector<int>>graph;
vector<int>giftScore;

void splitFunc(string str)
{
    istringstream is;
    is.str(str);
    vector<string>ans;
    string sttt;
    while(getline(is,sttt,' '))
    {
        ans.push_back(sttt);
    }
    graph[FM[ans[0]]][FM[ans[1]]]+=1;
    graph[FM[ans[1]]][FM[ans[0]]]-=1;
    giftScore[FM[ans[0]]]+=1;
    giftScore[FM[ans[1]]]-=1;
}

int solution(vector<string> friends, vector<string> gifts) {
    int answer = 0;
    giftScore=vector<int>(friends.size(), 0);
    for(int i=0; i<friends.size(); i++)
    {
        FM.insert({friends[i],i});
    }
    graph=vector<vector<int>>(friends.size(),vector<int>(friends.size(),0));
    for(int i=0; i<gifts.size(); i++)
    {
        splitFunc(gifts[i]);
    }
    
    for (int i=0; i<friends.size(); i++)
    {
        int nowGift=0;
        for (int j=0; j<friends.size(); j++)
        {
            if (graph[i][j]>0)
            {
                nowGift+=1;
            }
            else if (graph[i][j]==0)
            {
                if (giftScore[i]>giftScore[j])
                {
                    nowGift+=1;
                }
            }
        }
        if (nowGift>answer)
        {
            answer=nowGift;
        }
    }
    return answer;
}

 

---

 

 

문제보다 문제를 풀기 위해 map과 getline을 사용하기 위해 stringstream을 사용하는게 더 어려웠던 문제였다

 

프로그래머스