[Programmers Lv. 1] C++: 가장 많이 받은 선물

프로그래머스 Lv.1에 있는 "가장 많이 받은 선물" 문제에 대한 풀이 및 탐구에 대한 기록.

정답률 24%.

목   차

 

문제 분석

Input: 

• friends: 친구 이름 목록.
• gifts: 선물을 주고 받은 기록. (ex: muzi frodo = muzi가 frodo에게 선물을 주었다.)

Output: 

• result: 다음달에 선물을 가장 많이 받을 친구가 받는 선물의 개수.

A -> B 5회, B -> A 3회  라면, 다음 달엔 B-> A 1회.

0회 또는 같다면, 선물 지수(받은 횟수 - 준 횟수)에 따라 선물을 받는다.

선물 지수도 같다면 다음 달에 주고 받지 않음.

문제 풀이

초안

소요 시간: 55분 34초.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<string> friends, vector<string> gifts) {
    const int friendsNum = friends.size();
    int** giftArr = new int* [friendsNum];
    for (int i = 0; i < friendsNum; ++i) {
        giftArr[i] = new int[friendsNum]();
    }

    for (int i = 0; i < gifts.size(); i++) {
        size_t spaceIndex = gifts[i].find(" ");

        string giver = gifts[i].substr(0, spaceIndex);
        auto giverIt = find(friends.begin(), friends.end(), giver);
        int giverIdx = distance(friends.begin(), giverIt);

        string receiver = gifts[i].substr(spaceIndex + 1, gifts[i].length() - (spaceIndex));
        auto receiverIt = find(friends.begin(), friends.end(), receiver);
        int receiverIdx = distance(friends.begin(), receiverIt);

        giftArr[giverIdx][receiverIdx]++;
    }

    int* receiveArr = new int[friendsNum]();
    for (int i = 0; i < friends.size(); i++) {
        for (int j = i + 1; j < friends.size(); j++) {
            int give = giftArr[i][j];
            int receive = giftArr[j][i];

            if (give > receive) {
                receiveArr[i]++;
            }
            else if (give < receive) {
                receiveArr[j]++;
            }
            else {
                int index1 = 0; int index2 = 0;
                for (int k = 0; k < friends.size(); k++) {
                    index1 += giftArr[i][k];
                    index2 += giftArr[j][k];
                }

                for (int k = 0; k < friends.size(); k++) {
                    index1 -= giftArr[k][i];
                    index2 -= giftArr[k][j];
                }

                if (index1 == index2) continue;
                else if (index1 > index2) {
                    receiveArr[i]++;
                }
                else {
                    receiveArr[j]++;
                }
            }
        }
    }

    int result = receiveArr[0];
    for (int i = 1; i < friendsNum; i++) {
        if (result < receiveArr[i])
            result = receiveArr[i];
    }
    
    for (int i = 0; i < friendsNum; ++i) {
        delete[] giftArr[i];
    }
    delete[] giftArr;
    delete[] receiveArr;

    return result;
}

 

리팩토링된 답안

두 번째 답안

코드에 대한 상세 분석. 왜 이렇게 바꾸었는지. 

 

추가 대제목

느낀 점

줄글 형.