[leetcode]Filter Restaurants by Vegan-Friendly, Price and Distance

유의할점

restaurants.sort(key=lambda r:(-r[1],-r[0])) # lambda식 사용.

풀이

두가지 풀이가 있다.

1. 소팅 → 필터 적용하면서 ID값만 추출
2. 필터 적용 → 소팅 → ID값 접근

1번의 경우는 소팅에 O(nlogn)의 시간복잡도를 가진다. 필터 적용하면서 ID값 추출에는 O(n)의 시간복잡도를 가진다.

2번의 경우에는 필터를 적용해 O(n)의 시간복잡도를 가진다. 소팅에 O(nlogn)의 시간복잡도를 가진다. 이때 필터링이 많이 되었다면 n의 크기가 줄어서 소팅에 적은 시간이 걸렸을것이다. 소팅된 리스트에서 ID값을 추출하는 과정은 O(n)의 시간복잡도를 가지게 된다.

따라서 각각의 경우에 장단점이 존재한다. 필터링할것이 많은 경우 2번의 경우가 최선이고 필터링할것이 없는 경우 1번이 최선이다.

코드

Python

class Solution:
    def filterRestaurants(self, restaurants: List[List[int]], veganFriendly: int, maxPrice: int, maxDistance: int) -> List[int]:
        restaurants.sort(key=lambda r:(-r[1],-r[0]))
        return [i for (i,r,v,p,d) in restaurants if veganFriendly <= v and p <= maxPrice and d <= maxDistance]