[프로그래머스] 가장 많이 받은 선물

코딩테스트 연습2024 KAKAO WINTER INTERNSHIP 가장 많이 받은 선물

 

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

프로그래머스

 

문제해결능력을 보는 문제인가..?

흠.. 어떤 알고리즘 기법인지 잘 모르겠다.

지나가다가 알려주시고 싶은 분은 댓글 남겨주세요.

더 효율적인 방법이 있다면 그것도 알려주세요. 감사합니다!

 

 

[해결 방법]

1. friend 의 데이터를 쉽게 다루기 위해 이름을 Index 로 변환했다.

2. gift로 들어온 값을 통해 선물을 주고받은 내역을 저장하고, 선물 지수를 저장한다. 

- 선물 주고 받은 내역은 2차원 배열로 저장했다.

- 준 사람의 선물지수값은 하나 올리고

- 받은 사람의 선물 지수는 하나 내린다

3. 2번에서 저장한 데이터를 통해 규칙에 따라 각 사람마다 선물을 몇개 받는지 array를 만들고,

문제에서는 Max Value를 return하는 것이기 때문에 sort를 통해 가장 첫번째 value를 Return하는 것으로 만들어주었다.

 

 

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

using namespace std;
static std::map<std::string, int> personKey;
static std::vector<std::vector<int>> giftContent;

static std::vector<int> giftValue;
static std::vector<int> answerKey;

int getKey(std::string name) {
    return personKey[name];
}

void initKey(vector<string> friends) {
    int idx = 0;
    for (auto i : friends) {
        personKey[i] = idx;
        idx++;
    }
    
    auto size = friends.size();
    for (int i = 0; i < size; i++) {
        std::vector<int> arr1;
        for (int j = 0; j < size; j++) {
            arr1.push_back(0);
        }
        giftContent.push_back(arr1);
    }
    giftValue.resize(size);
    answerKey.resize(size);
}

void makeArray(vector<string> gifts) {
    for (auto i : gifts) {
        auto blank = i.find(" ");
        auto give = i.substr(0, blank);
        auto given = i.substr(blank+1);
        
        int giveKey = getKey(give);
        int givenKey = getKey(given);

        giftContent[giveKey][givenKey] += 1;
        giftValue[giveKey]++;
        giftValue[givenKey]--;
    }
    
}


int getMaxValue(int size) {
    int max = 0;
    for (int i = 0; i < size; i++) {
        for (int j = i; j < size; j++) {
            if (i != j) {
                if (giftContent[i][j] > giftContent[j][i]) {
                    answerKey[i]++;
                } else if (giftContent[i][j] < giftContent[j][i]) {
                    answerKey[j]++;
                } else if (giftContent[i][j] == giftContent[j][i]) {
                    if (giftValue[i] > giftValue[j]) {
                        answerKey[i]++;
                    } else if (giftValue[i] < giftValue[j]) {
                        answerKey[j]++;
                    }
                } else {
                    // do nothing
                }
            }
        }
    }

    std::sort(answerKey.begin(), answerKey.end(), std::greater());

    return answerKey[0];
}

int solution(vector<string> friends, vector<string> gifts) {
    int answer = 0;
    initKey(friends);
    makeArray(gifts);
    
    answer = getMaxValue(friends.size());
    return answer;
}

 

 

나중에 알게 된 내용인데 (이건 나의 무지에서 나온 잘못이다)

STL에서 제공해주는 max_element, min_element, maxmin_element 가 있어서 훨씬 효율적인 것 같다

 

sort 의 경우 불필요하게 데이터 전체를 정렬하며, 시간복잡도가 O(nlogn) 이라고 하는데

max_element 의 경우 O(n) 의 시간복잡도를 가진다고 한다. 

졸업한지 10년이 넘어서 까먹은 그래프..

 

maxmin_element 는

first, second로 접근하면 되는 것 같다. 

#include <iostream>
#include <vector>
#include <algorithm> // std::max_element, std::min_element, std::minmax_element

int main() {
    std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6, 5};

    // 1. std::max_element 사용 (최댓값 찾기)
    auto maxIt = std::max_element(vec.begin(), vec.end());
    if (maxIt != vec.end()) {
        std::cout << "Max element: " << *maxIt << std::endl;
    }

    // 2. std::min_element 사용 (최솟값 찾기)
    auto minIt = std::min_element(vec.begin(), vec.end());
    if (minIt != vec.end()) {
        std::cout << "Min element: " << *minIt << std::endl;
    }

    // 3. std::minmax_element 사용 (최솟값과 최댓값 동시에 찾기)
    auto minmaxIt = std::minmax_element(vec.begin(), vec.end());
    if (minmaxIt.first != vec.end() && minmaxIt.second != vec.end()) {
        std::cout << "Min element: " << *minmaxIt.first << std::endl;
        std::cout << "Max element: " << *minmaxIt.second << std::endl;
    }

    return 0;
}

 

다시 또 까먹을까봐 적는..

 

sort 로 접근하는 방법은

vector.back() vs vector.front()