귤귤나무 일지
LeetCode - 1710. Maximum Units on a Truck 본문
처음 생각했던 풀이는 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
정렬
'Programming > Coding Problems' 카테고리의 다른 글
LeetCode - 49. Group Anagrams (0) | 2024.11.12 |
---|---|
LeetCode - 2357. Make Array Zero by Subtracting Equal Amounts (0) | 2024.11.11 |
LeetCode - 1603. Design Parking System (0) | 2024.11.11 |
LeetCode - 13. Roman to Integer (0) | 2024.11.11 |
LeetCode - 9. Palindrome Number (1) | 2024.11.10 |