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

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

프로그래머스

---

1. Logic

string과 숫자를 가지고 놀아야 하기 때문에 map자료구조가 적절할 것이라고 판단했다. 

 

friends배열에 있는 순서대로 인덱스를 매겨주고 서로 몇번 주고받았는지 확인했다.

핵심은 2중 for문에 있는데, 이중 계산을 막기 위해 선물을 받는 경우만 계산해줬다 

코드는 아래와 같다.

---

2. Code

#include <bits/stdc++.h>

using namespace std;

map<string, int> nameToIdx;
int giftArr[51][51];
map<string, int> give;
map<string, int> receive;


int solution(vector<string> friends, vector<string> gifts) {
    int answer = 0;
    
    for(int i = 0; i < friends.size(); i++) {
        nameToIdx[friends[i]] = i;
    }
    
    for(int i = 0; i < gifts.size(); i++) {
        string giveName = "";
        string temp = "";
        for(int j = 0; j < gifts[i].length(); j++) {
            if(gifts[i][j] == ' ') {
                giveName = temp;
                temp = "";
                continue;
            }
            temp += gifts[i][j];
        }
        giftArr[nameToIdx[giveName]][nameToIdx[temp]]++;
        give[giveName]++;
        receive[temp]++;
    }
    
    int cur = friends.size();    
    
    for(int i = 0; i < cur; i++) {
        int giftTemp = 0;
        for(int j = 0; j < cur; j++) {
            if(giftArr[i][j] > giftArr[j][i]) {
                giftTemp++;
            }
            else if(giftArr[i][j] == giftArr[j][i]) {
                if(give[friends[i]]-receive[friends[i]] > give[friends[j]] -receive[friends[j]]) {
                    giftTemp++;
                }
            }
        }
        answer = max(answer, giftTemp);
    }
    
    return answer;
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐