문제 설명

1. 배열로 friends, gifts가 주어진다.
2. 주고 받은 적이 있는 사이라면 더 적게 받았던 쪽이 다음 달에 1개의 선물을 받는다.
3. 주고 받은 적이 없는 사이거나 동일한 숫자를 받았다면, 선물 지수가 더 높은 친구들에게 하나씩 받는다.

문제 해결 전략

표를 이용한다.

각 친구들끼리의 선물 관계와 선물 지수를 표(2차원 배열)을 이용해서 관리한다.

for(int i =0; i < friends.size(); i++){
        string name = friends[i];
        names[name] = i;        
}
    
for(int i =0;i<gifts.size(); i++){
        string tg = gifts[i];
        int find_space = tg.find(' ');
        string from_friend = tg.substr(0, find_space);
        string to_friend = tg.substr(find_space+1);
        
        int fIdx = names[from_friend];
        int tIdx = names[to_friend];
        BOARD[fIdx][tIdx]++;
        people[fIdx]++;
        people[tIdx]--;
    }

위의 코드를 통해서 표를 만들었다..
입력으로 들어온 friends를 순서대로 0 ~ friends.size() - 1 인덱스로 지정해줬다.
muzi frodo라는 입력은 muzi 가 frodo에게 준 것으로 코딩을 한다면 쉽게 표를 만들 수 있다.
해당 과정에서 people이라는 배열을 사용해서 선물을 준 사람(muzi)은 증가시키고 받은 사람(frodo)은 감소 시켰다.

substr 메서드를 이용해서 공백을 기준으로 파싱했다.

선물 주고 받기

for(int i = 0; i < friends.size(); i++){
    int ret = 0;
    int maxGift = -1;
    int y,x;
    for(int j = 0; j < friends.size(); j++){
        if(i==j)
            continue;
        if(BOARD[i][j] > BOARD[j][i])
            ret++;
        if(BOARD[i][j] == BOARD[j][i]){
            if(people[i] > people[j])
                ret++;
        }
    }
    answer = max(answer, ret);
}

위에서 만든 표를 토대로 단순히 2중 반복문을 사용해서 구현했다.
첫 번째 조건인if(i==j)는 본인이기 때문에 continue 로 넘어간다.

두 번째 조건에서는 i와 j중에 서로 주고 받은 사람끼리의 비교다. i가 j한테 더 받았다면 i를 증가시킨다. 어차피 그 다음 j와 i를 비교하게 될 때는 증가되지 않는다.

세 번째 조건은 같은 경우(주고 받은 적이 없거나, 동일하게 주고 받았다면) 선물 지수를 비교해서 결과를 증가시킨다.

코드

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

using namespace std;

map<string,int> names;
int BOARD[51][51];
int people[51];

int solution(vector<string> friends, vector<string> gifts) {
    int answer = 0;
    for(int i =0; i < friends.size(); i++){
        string name = friends[i];
        names[name] = i;        
    }
    
    for(int i =0;i<gifts.size(); i++){
        string tg = gifts[i];
        int find_space = tg.find(' ');
        string from_friend = tg.substr(0, find_space);
        string to_friend = tg.substr(find_space+1);
        
        int fIdx = names[from_friend];
        int tIdx = names[to_friend];
        BOARD[fIdx][tIdx]++;
        people[fIdx]++;
        people[tIdx]--;
    }
    
    
    for(int i = 0; i < friends.size(); i++){
        int ret = 0;
        int maxGift = -1;
        int y,x;
        for(int j = 0; j < friends.size(); j++){
            if(i==j)
                continue;
            if(BOARD[i][j] > BOARD[j][i])
                ret++;
            if(BOARD[i][j] == BOARD[j][i]){
                if(people[i] > people[j])
                    ret++;
            }
        }
        answer = max(answer, ret);
    }
    return answer;
}

소감

Lv1 치고는 조금 복잡했던 것 같다.
이 문제는 단순 구현이라도 조금 더 신경쓸 게 있는데, Lv2가 좀 더 맞는 거 같기도 하다.
그래도 문제에서 하라는 대로 따라하면 쉽게 구현할 수 있는듯

Reference
https://school.programmers.co.kr/learn/courses/30/lessons/258712
Code
https://github.com/im2sh/Algorithm/blob/main/Programmers/%5B2024%20KAKAO%20WINTER%20INTERNSHIP%5D/%5BLv1%5D%20%EA%B0%80%EC%9E%A5%20%EB%A7%8E%EC%9D%B4%20%EB%B0%9B%EC%9D%80%20%EC%84%A0%EB%AC%BC.cpp