레스토랑 정보가 담긴 배열이 있다고 가정해 보겠습니다. 각 레스토랑 restaurants[i]는 [id, rating(평점), veganFriendly(채식 친화 여부), price(가격), distance(거리)] 형태의 데이터를 담고 있습니다. 이번 문제에서는 세 가지 필터 조건을 사용해 레스토랑을 걸러내야 합니다.
채식 친화 필터(veganFriendly): 값이 true(1)이면 채식 친화로 표시된 레스토랑만 포함하고, false(0)이면 모든 레스토랑을 포함할 수 있습니다.
최대 가격 필터(maxPrice): 고려 대상 레스토랑의 가격 상한값입니다.
최대 거리 필터(maxDistance): 고려 대상 레스토랑의 거리 상한값입니다.
필터링을 마친 후에는 레스토랑 ID 배열을 반환해야 하며, 평점(rating)이 높은 순서대로 정렬합니다. 평점이 같은 경우에는 ID가 큰 순서대로 정렬합니다. 편의상 veganFriendly 값은 참일 때 1, 거짓일 때 0으로 표현합니다.
예시
입력이 다음과 같다고 해보겠습니다.
restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 1, maxPrice = 50, maxDistance = 10
이때 출력은 [3,1,5]입니다. 각 레스토랑의 정보를 살펴보면 다음과 같습니다.
레스토랑 1: id=1, rating=4, veganFriendly=1, price=40, distance=10
레스토랑 2: id=2, rating=8, veganFriendly=0, price=50, distance=5
레스토랑 3: id=3, rating=8, veganFriendly=1, price=30, distance=4
레스토랑 4: id=4, rating=10, veganFriendly=0, price=10, distance=3
레스토랑 5: id=5, rating=1, veganFriendly=1, price=15, distance=1
veganFriendly = 1, maxPrice = 50, maxDistance = 10 조건으로 필터링하면 레스토랑 3, 1, 5만 남습니다. 이를 평점 내림차순으로 정렬한 결과가 바로 [3,1,5]입니다.
풀이 접근 방법
(id, rating) 쌍을 저장할 임시 배열 temp를 만들고, n을 레스토랑 배열의 크기로 설정합니다.
i를 0부터 n-1까지 반복하며 다음 조건을 확인합니다.
vf == 0 또는 r[i][2] == vf를 만족하고, 동시에 r[i][3] <= mp 그리고 r[i][4] <= md를 만족하면
[r[i][0], r[i][1]]을 temp에 삽입합니다.
temp를 평점 기준 내림차순으로 정렬합니다.
결과를 담을 배열 ret을 생성합니다.
temp의 모든 요소에 대해 temp[i][0], 즉 레스토랑 ID를 ret에 삽입합니다.
ret을 반환합니다.
전체 시간 복잡도는 정렬 과정이 지배적이므로 O(n log n)이며, 공간 복잡도는 필터링 결과를 저장하는 데 O(n)입니다.
C++ 구현 예제
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
static bool cmp(vector <int> a, vector <int> b){
if(b[1] != a[1])return a[1] > b[1];
return a[0] > b[0];
}
vector<int>filterRestaurants(vector<vector<int>>& r, int vf, int mp, int md) {
vector < vector <int> > temp;
int n = r.size();
for(int i = 0; i < n; i++){
if((vf == 0 || r[i][2] == vf) && r[i][3] <= mp && r[i][4] <= md){
temp.push_back({r[i][0], r[i][1]});
}
}
sort(temp.begin(), temp.end(), cmp);
vector <int> ret;
for(int i = 0; i < temp.size(); i++)ret.push_back(temp[i][0]);
return ret;
}
};
main(){
vector<vector<int>> v = {{1,4,1,40,10},{2,8,0,50,5},{3,8,1,30,4},{4,10,0,10,3},{5,1,1,15,1}};
Solution ob;
print_vector(ob.filterRestaurants(v, 1, 50, 10));
}입력
[[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]] 1 50 10
출력
[3,1,5]