[LeetCode] 1828번: 원 안의 점 개수

Hint

1. 원과 점들의 최대 개수가 각각 500개이기 때문에 for문 2개를 사용해서 일일이 비교해도 된다
2. Follow up에 O(n)으로 풀어보라고 되어있지만 이건 나중에 도전...^^

 

LeetCode 1828번: Queries on Number of Points Inside a Circle (풀어보기)

class Solution:
    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:
        # points를 x, y 순서로 작은 숫자부터 큰 숫자까지 정렬한다
        points = sorted(points, key=lambda x: (x[0],x[1]))
        
        answer = []
        for query in queries:
            x, y, r = query
            count = 0
            
            for point in points:
                px, py = point
                
                # points를 정렬했기 때문에 원의 최대 x, y를 넘어가는 점 이후로는 확인 할 필요가 없다
                if (px >= x + r) & (py >= y + r):
                    break
                
                # 원 중심에서 point까지의 길이가 반지름보다 같거나 작을 때만 원 안에 있는 것이기 때문에 개수에 포함한다
                if r >= ((px-x)**2 + (py-y)**2)**0.5:
                    count += 1
            
            answer.append(count)
        
        return answer