평면 위에 서로 다른 위치에 있는 n개의 점이 주어졌다고 가정해 봅시다. 이때 부메랑(boomerang)은 세 점으로 이루어진 순서쌍 (i, j, k) 중에서 i와 j 사이의 거리가 i와 k 사이의 거리와 동일한 경우를 말합니다. 즉, 한 점을 기준으로 양쪽에 같은 거리만큼 떨어진 두 점이 있는 V자 형태의 구조입니다. 우리가 구해야 할 것은 이러한 부메랑의 총개수입니다.
예를 들어 입력이 [[0,0], [1,0], [2,0]]이라면 출력은 2가 됩니다. 만들어질 수 있는 두 부메랑은 [[1,0],[0,0],[2,0]]과 [[1,0],[2,0],[0,0]]입니다. 동일한 세 점이라도 j와 k의 순서가 바뀌면 서로 다른 부메랑으로 계산한다는 점에 유의하세요.
알고리즘 접근 방법
이 문제의 핵심은 각 점으로부터 같은 거리에 있는 점들을 그룹으로 묶는 것입니다. 어떤 점을 기준으로 거리가 d인 점이 n개 존재한다면, 이들 중 순서를 고려해 두 점 (j, k)를 선택하는 경우의 수는 n × (n − 1)가 됩니다. 이 값을 모든 기준점과 거리 그룹에 대해 더하면 최종 답을 구할 수 있습니다.
구체적인 풀이 과정은 다음과 같습니다.
- counter_of_boomerangs를 0으로 초기화합니다.
- points 배열의 각 점 point_1에 대해 반복합니다.
- x1, y1 = point_1로 좌표를 추출합니다.
- 거리별 등장 횟수를 저장할 맵 distance_count_dict를 생성합니다.
- points 배열의 각 점 point_2에 대해 반복합니다.
- x2, y2 = point_2로 좌표를 추출합니다.
- diff_x := x2 − x1
- diff_y := y2 − y1
- dist := diff_x² + diff_y² (제곱근을 생략해도 거리 비교에는 지장이 없습니다)
- distance_count_dict[dist] 값을 1 증가시킵니다.
- distance_count_dict의 각 거리 d에 대해 다음을 수행합니다.
- n := distance_count_dict[d]
- counter_of_boomerangs := counter_of_boomerangs + n × (n − 1)
- counter_of_boomerangs를 반환합니다.
예제 코드
아래 파이썬 구현을 살펴보면 이해하는 데 도움이 됩니다.
from collections import defaultdict
class Solution:
def numberOfBoomerangs(self, points):
counter_of_boomerangs = 0
for point_1 in points:
x1, y1 = point_1
distance_count_dict = defaultdict(int)
for point_2 in points:
x2, y2 = point_2
diff_x = x2 - x1
diff_y = y2 - y1
dist = diff_x ** 2 + diff_y ** 2
distance_count_dict[dist] += 1
for d in distance_count_dict:
n = distance_count_dict[d]
counter_of_boomerangs += n * (n - 1)
return counter_of_boomerangs
ob = Solution()
print(ob.numberOfBoomerangs([[0,0],[1,0],[2,0]]))입력
[[0,0],[1,0],[2,0]]
출력
2
복잡도 분석
모든 점 쌍 사이의 거리를 계산해야 하므로 시간 복잡도는 O(n²)이며, 각 기준점마다 거리 정보를 저장하는 딕셔너리가 필요하기 때문에 공간 복잡도는 O(n)입니다. 또한 실제 거리 대신 제곱 거리(squared distance)를 사용하면 제곱근 연산과 부동소수점 오차를 피할 수 있어 정확한 비교가 가능하다는 장점이 있습니다.