두 개의 리스트 sales와 buyers가 주어졌다고 가정해 보겠습니다. sales의 각 요소는 [day, price] 형태의 두 값으로 구성되며, 해당 패키지가 지정된 날에만 특정 가격으로 판매된다는 의미입니다. buyers의 각 요소는 [payday, amount] 형태로, 해당 구매자가 payday 당일부터 amount만큼의 금액을 사용할 수 있음을 나타냅니다.
각 구매자는 최대 한 개의 패키지만 구매할 수 있고, 각 패키지 역시 한 명에게만 판매될 수 있습니다. 이 조건에서 성사될 수 있는 거래, 즉 판매될 수 있는 패키지의 최대 개수를 구하는 것이 문제입니다.
예를 들어 입력이 sales = [[0, 5], [0, 5], [0, 6], [1, 4], [1, 5], [3, 4]], buyers = [[0, 4], [0, 6], [1, 5]]라면 출력은 3이 됩니다. 첫 번째 구매자는 [1, 4] 패키지를, 두 번째 구매자는 [0, 6] 패키지를, 세 번째 구매자는 [1, 5] 패키지를 각각 구매할 수 있기 때문입니다.
문제 해결 접근 방법
이 문제는 그리디(Greedy) 알고리즘과 항상 정렬 상태를 유지하는 multiset 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 판매하기 어려운 패키지, 즉 판매일이 빠르거나 가격이 높은 패키지를 먼저 처리하고, 매칭할 때는 조건을 충족하는 구매자 중 가장 적은 금액을 가진 사람을 선택해 남은 선택지를 최대한 유연하게 유지하는 것입니다.
단계별 과정은 다음과 같습니다.
결괏값 ret을 0으로 초기화합니다.
buyers 배열을 payday 기준으로 오름차순 정렬하고, payday가 같으면 amount 기준으로 정렬합니다.
multiset 타입의 pq를 정의합니다.
sales 배열을 날짜 오름차순으로, 같은 날짜라면 가격 내림차순으로 정렬합니다.
인덱스 i를 0으로 초기화합니다.
sales의 각 항목 it에 대해 다음을 반복합니다.
i가 buyers의 크기보다 작고 buyers[i][0] <= it[0]을 만족하는 동안 buyers[i][1]을 pq에 삽입하고 i를 1씩 증가시킵니다. 즉, 해당 패키지가 판매되는 시점까지 구매 자금을 확보한 구매자들을 후보군에 추가합니다.
pq에서 it[1] 이상인 값 중 가장 작은 값의 위치(lower_bound)를 찾아 j에 저장합니다.
j가 유효한 위치라면 ret을 1 증가시키고 pq에서 해당 요소를 제거합니다. 이는 패키지 가격을 감당할 수 있는 구매자 중 여유 자금이 가장 적은 사람과 매칭한다는 의미입니다.
모든 패키지를 확인한 뒤 ret을 반환합니다.
예제 코드
더 나은 이해를 돕기 위해 다음 C++ 구현을 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
static bool cmp(vector<int>& a, vector<int>& b) {
return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
}
int solve(vector<vector<int>>& sales, vector<vector<int>>& buyers) {
int ret = 0;
sort(buyers.begin(), buyers.end());
multiset<int> pq;
sort(sales.begin(), sales.end(), cmp);
int i = 0;
for (auto& it : sales) {
while (i < buyers.size() && buyers[i][0] <= it[0]) {
pq.insert(buyers[i][1]);
i++;
}
auto j = pq.lower_bound(it[1]);
if (j != pq.end()) {
ret++;
pq.erase(j);
}
}
return ret;
}
};
int solve(vector<vector<int>>& sales, vector<vector<int>>& buyers) {
return (new Solution())->solve(sales, buyers);
}
int main(){
vector<vector<int>> sales = {{0, 5},{0, 5},{0, 6},{1, 4},{1, 5},{3, 4}};
vector<vector<int>> buyers = {{0, 4},{0, 6},{1, 5}};
cout << solve(sales, buyers);
}
입력
{{0, 5},{0, 5},{0, 6},{1, 4},{1, 5},{3, 4}}, {{0, 4},{0, 6},{1, 5}}
출력
3