[Leetcode]1828. Queries on Number of Points Inside a Circle

문제 요약

• 알고리즘 분류: 기하학
• 난이도: Medium
• 문제내용:
  • [x, y]로 점으로 구성된 points와 [x, y, r]로 원으로 구성된 queries가 주어진다. 
  • queries로 주어진 [x, y, r]은 x, y 위치를 의미하고 r은 원의 반지름을 의미한다. 
  • 각 query 원 안에서 points 점들이 몇개 포함되는지 반환 하는 함수를 만들어라.
• 사이트 주소: https://leetcode.com/problems/queries-on-number-of-points-inside-a-circle/description/

문제풀이 

 이번 문제는 기하학 문제이고 원에 대한 개념만 알면 문제 풀기가 쉽다.

 원은 중심점과 반지름 r로 이루어 져 있다. 원안에 각 point가 포함되어 있는지 여부는 원 중심점과 point 거리가 r보다 작으면 point가 포함되어 있는지 알수 있다.

  그럼 두 점 사이의 거리 구하는 공식만 알면 되는데 두 점 거리가 반 지름 이하인 식은 아래 와 같다.

 위에 루트 씌우는 것은 Math 모듈을 사용 해야 하고 정수가 아닌 실수인 점을 계산하는게 귀찮아서 아래 식을 사용하면 코드 구현하는데 조금 편할 것이다.

각 점이 위 공식에 참인 개수만 구하면 구현은 끝이다. 이렇게 구현했을때 시간 복잡도는 각 점과 원을 고려하면 O(N^2)만큼 나올것이다. 

Code

Python

class Solution:
    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:
        result = list() # 반환할 리스트

        for x2, y2, r in queries:
            count = 0 # count 0으로 초기화
            for x1, y1 in points:
                # 원 포함 되는 경우 (x1, y1) (x2, y2) 거리가 원의 반지름 보다 작을때
                # (x1 - x2) ^ 2 + (y1 - y2) ^ 2 <= r ^2
                count += (x1 - x2) ** 2 + (y1 - y2) ** 2 <= r ** 2
            result.append(count)

        return result

Java

class Solution {
    public int[] countPoints(int[][] points, int[][] queries) {
        int querySize = queries.length; // 쿼리 길이
        int[] result = new int[querySize]; // 반환 배열

        int count;
        for(int i = 0; i < querySize; i++){
            count = 0; // count 0으로 초기화
            for(int[] point : points){
                // 원 포함 되는 경우 (x1, y1) (x2, y2) 거리가 원의 반지름 보다 작을때
                // (x1 - x2) ^ 2 + (y1 - y2) ^ 2 <= r ^2
                count += Math.pow(point[0] - queries[i][0], 2) + Math.pow(point[1] - queries[i][1], 2) <= Math.pow(queries[i][2], 2) ? 1 : 0;
            }

            result[i] = count;
        }
        return result;
    }
}