[2250] Count Number of Rectangles Containing Each Point | Medium | contest 290

yoongyum·2022년 4월 25일
0

코딩테스트 🧩

목록 보기
20/47
post-thumbnail

남은 두 문제는 저는 풀지 못했습니다.
다른 사람들의 코드를 보면서 분석해보겠습니다.

🔎문제설명

좌표가 들어있는 point = []와 사각형들이 들어있는 rectangles = []가 주어집니다.
point에 들어있는 각 좌표마다.
몇개의 사각형들에 포함되는 지 반환하는 문제입니다.

Example 1

Input: rectangles = [[1,2],[2,3],[2,5]], points = [[2,1],[1,4]]
Output: [2,1]

(2,1) 좌표는 두개의 사각형에 포함되고 (1,4)좌표는 1개의 사각형에만 포함되어 [2,1]을 반환합니다.


Example 2

Input: rectangles = [[1,1],[2,2],[3,3]], points = [[1,3],[1,1]]
Output: [1,3]

쉬워보이겠죠.

제한조건을 보기전까진
bruteforce로 풀면 25억번 루프를 돌아서 시간초과납니다. (경험담이구요.)

제한사항

  • 1 ≤ rectangles.length, points.length ≤ 51045 * 10^4
  • rectangles[i].length == points[j].length == 2
  • 1 ≤ li, xj ≤ 10910^9
  • 1 ≤ hi, yj ≤ 100
  • All the rectangles are unique.
  • All the points are unique.

🧊 파이썬 코드

분석을 해본 결과 이문제는 이진탐색으로 많이 푸는 것을 확인했습니다.
이진탐색을 하려면 정렬돼있는 리스트가 필요합니다. 어떻게 이진탐색을 쓰는 지도 알아야합니다.

먼저, 제한조건을 보면 특이한게 있습니다. 사각형의 밑변의 크기는 최대 10910^9인데
높이는 최대 100으로 크기가 매우 작습니다.

따라서 높이를 key로 삼아서 해당 높이 마다 밑변의 사각형이 존재하면 리스트에 추가하는 방식으로 만듭니다.

그리고 각 key가 가리키는 리스트를 정렬하고 이진탐색을 돌리는 원리입니다.

class Solution:
    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:
        from bisect import bisect

        rect_map = defaultdict(list)

        for l, h in rectangles:
            rect_map[h].append(l)
		
        for k , vl in rm.items():
            rect_map[k].sort()
        
        def contains(x, y):
            count = 0

            for height, widths in rect_map.items():
                if height >= y:
                    count += len(widths) - bisect_left(widths, x)

            return count

        res = []

        for point in points:
            x, y = point
            res.append(contains(x, y))

        return res

TC : O(MlogN)O(MlogN)


💡 defaultdict()

defaultdict()는 딕셔너리를 만드는 dict클래스의 서브 클래스입니다.

딕셔너리와 다른점은 처음 키를 지정할 때 값을 주지 않으면 해당 키에 대한 값을 default값을 지정합니다.

list, set 등으로 초기화가 가능하기 때문에 용도가 넓습니다.

예제 코드

int:

name = 'kimyoongyum'
name_dict = defaultdict(int) #자동으로 0이 채워집니다.

for i in name:
	name_dict[i] += 1
    
## 출력결과
defaultdict(<class 'int'>, {'k': 1, 'i': 1, 'm': 2, 'y': 2, 'o': 2, 'n': 1, 'g': 1, 'u': 1})

list:

rectangles = [[1,2],[2,3],[2,5],[3,3]] #(가로, 세로)
rect_dict = defaultdict(list)

for x, y in rectangles:
	rect_dict[y].append(x)
    
## 출력결과
defaultdict(<class 'list'>, {2: [1], 3: [2, 3], 5: [2]})

set:

set은 위 list에서 중복제거 하는 원리라 따로 코드를 짜진 않겠습니다.

💡 bisect()

TC : O(logN)O(logN)

bisect는 이진 탐색을 할 수 있게 해주는 함수입니다.

  • bisect_left(iterable, x)

    정렬된 리스트에서 x가 삽입될 수 있는 가장 왼쪽 인덱스 반환

  • bisect_right(iterable, x)

    정렬된 리스트에서 x가 삽입될 수 있는 가장 오른쪽 인덱스 반환

0개의 댓글