Notice
Recent Posts
Recent Comments
Link
«   2024/12   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
Tags
more
Archives
Today
Total
관리 메뉴

귤귤나무 일지

LeetCode - 1710. Maximum Units on a Truck 본문

Programming/Coding Problems

LeetCode - 1710. Maximum Units on a Truck

귤귤나무 2024. 11. 11. 21:26

처음 생각했던 풀이는 boxTypes[i] = [numberOfBoxes, numberOfUnitsPerBox]니까,

numberOfUnitsPerBox 기준으로 내림차순으로 정렬하고, 맨 앞에서부터 truckSize 개수만큼 더해야겠다!였다.

 

중간에 테스트 케이스 1개에서 runtime Error가 났는데, boxTypes에서 주어진 모든 box들의 개수의 합이 truckSize보다 작을 수 있는 경우를 고려하지 못 했다.

그래서 수정해서 완성한 풀이는 다음과 같다.

class Solution {
public:
    static bool comp(vector<int> a, vector<int> b) {
        if (a[1] > b[1]) {
            return true;
        }
        return false;
    }

    int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
        sort(boxTypes.begin(), boxTypes.end(), comp);
        int answer = 0;
        int index = 0;
        while(truckSize > 0 && index < boxTypes.size()) {
            answer += boxTypes[index][1];
            boxTypes[index][0]--;
            truckSize--;
            if (boxTypes[index][0] <= 0)
                index++;
        }
        return answer;
    }
};

이렇게 했더니 시간이 오래 걸렸다.

그래서 다른 방법을 생각한 게, while loop에서 1번씩 더하면서 루프를 도는 게 아니라 루프 1번마다 boxType 1개를 보고 그 개수랑 남은 truckSize 개수 비교해서 똑같은 크기의 box는 다같이 넣어야겠다!이다.

 

두 번째 풀이)

class Solution {
public:
    static bool comp(vector<int> a, vector<int> b) {
        if (a[1] > b[1]) {
            return true;
        }
        return false;
    }

    int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
        sort(boxTypes.begin(), boxTypes.end(), comp);
        int answer = 0;
        for (int i = 0; i < boxTypes.size(); i++) {
            if (truckSize >= boxTypes[i][0]) {
                answer += boxTypes[i][0] * boxTypes[i][1];
                truckSize -= boxTypes[i][0];
            } else {
                answer += truckSize * boxTypes[i][1];
                break;
            }
        }
        return answer;
    }
};

많이 줄어들진 않았다..

이에 대한 변형으로 if, else를 쓰지 말고 애초부터 for문 안을 이렇게 바꿀 수 있다.

int boxCount = min(truckSize, boxTypes[i][0]);
answer += boxCount * boxTypes[i][1];
truckSize -= boxCount;
if (truckSize == 0) break;

 

근데 이것도 그렇게 빨라지진 않았다.

 

그래서 결국 마지막엔 또 해설을 봤다..!

해설에선 c++의 priority_queue를 사용했다.

class Solution {
public:
    int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
        priority_queue<vector<int>, vector<vector<int>>, Comparator> queue;
        for (auto boxType : boxTypes) {
            queue.push(boxType);
        }
        int unitCount = 0;
        while (!queue.empty()) {
            vector<int> top = queue.top();
            queue.pop();
            int boxCount = min(truckSize, top[0]);
            unitCount += boxCount * top[1];
            truckSize -= boxCount;
            if(truckSize == 0)
                break;
        }
        return unitCount;
    }

    struct Comparator {
        bool operator()(vector<int> const& p1, vector<int> const& p2) {
            return p1[1] < p2[1];
        }
    };
};

 

여기서 알게된 priority_queue.

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

첫 번째 인자, class T는 priority_queue에서 각 노드에 저장할 단위.

두 번째 인자 class Container는 priority_queue 전체를 저장할 단위.

세 번째 인자 Compare는 비교할 기준.

 

여기서 헷갈렸던 건 세 번째 인자.

C++에서 sort는 마지막 Comp에서 위 문제 답에 있는 Comparator를 넣으면 오름차순으로 정렬된다.

그런데 priority_queue에서는 Compare에서 비교할 때 true를 반환하면 p1이 p2의 뒤에 위치하도록 한다.

그래서 priroity_queue와 sort에 넣을 Comp는 반대로 넣어야 되는 것 같다.

 

Key Idea

정렬