Number of Boomerangs

Number of Boomerangs

(https://leetcode.com/problems/number-of-boomerangs/)

좌표의 범위가 각각 -1000부터 1000까지 되는 point가 최대 500개가 있을 때, 서로 다른 point 끼리의 거리 중 같은 것의 개수를 구하는 문제였습니다.

예를 들어 (0,0), (0,1), (0,2) 라는 point가 존재할 때 (1,0)과 (0,0)의 거리는 1이고 (1,0)과 (2.0)의 거리고 1입니다. 이 때, i를 (1.0)으로 두고 j를 (0,0) 또는 (2,0), k를 (2,0) 또는 (0,0)이라고 할 때 i와 j의 거리 그리고 i와 k의 거리가 같습니다. 이렇게 같은 거리를 갖게 되는 경우가 세 점 사이에서 총 2가지가 발생하는데요. 이 2를 리턴하면 되는 것입니다.

처음에 생각할 때는 전체 포인트 끼리의 거리를 전부 구해서 이 값을 카운팅 하면 된다고 생각하였습니다. 그런데 계속 시간 초과가 떠서 수정을 7번 정도 해, 겨우 통과 했네요.

이차원 배열을 통해 각 포지션의 길이 값을 전부 저장했었는데 생각해보니, 키 값에 해당하는 포지션은 갖고 있을 필요가 없었습니다. 그래서 이를 일차원 배열로 고쳤더니 바로 Accepted가 떴습니다.

처음엔 전부를 카운팅 하는 것은 굉장히 비효율 적이고 오래 걸릴 작업이라고 생각했지만 점이 최대 500개고 500개씩 서로 경우의 수를 모두 곱해도 250000을 넘지 않았습니다. (중복을 포함해서 말이죠)

다만 쓸데 없는 계산, 예를 들어 점 사이의 거리를 구할 때 쓰는 공식에서 루트 값을 뺀다던지 하는 것은 제외했었네요.

한가지 더, pow를 빼고 ** operator로 바꾸니까 속도가 더 줄어들었습니다.

찾아보니 이런 글도 있더라구요. (http://stackoverflow.com/questions/20969773/exponentials-in-python-x-y-vs-math-powx-y)

백문이 불여일견이라고 코드는 다음과 같습니다.

from collections import defaultdict


class Solution(object):
    def numberOfBoomerangs(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        count = 0
        for p in points:
            x, y = p[0], p[1]
            count_list = defaultdict(int)
            for q in points:
                x2, y2 = q[0], q[1]
                if x == x2 and y == y2: continue
                length = get_length(x, x2, y, y2)
                count_list[length] += 1
            for k, v in count_list.items():
                count += permutation(v)

        return count


def permutation(v):
    # if v == 2: return 2 # useless
    return v * (v - 1)


def get_length(x, x2, y, y2):
    return (x - x2) ** 2 + (y - y2) ** 2

permutation 함수의 리턴 값은 같은 점들만이 존재하는 count_list에서 서로 다른 점들을 고른 것입니다. 

예를 들어 임의의 점 4개에서 기준이 되는 하나를 제외하면 총 3 개의 점이 남는데요. 이 때 기준 점과 3개의 점 사이의 경우의 수가 3 *2 가 되기 때문입니다. 다시 말하자면 기준 점 P라고 두었을 때 서로 다른 3개의 점이 각각 A,B,C가 있고 문제에서 중복을 포함하므로 (j와 k가 서로 바뀌어도 상관 없죠) 중복을 포함한 순열을 사용한 것입니다.

(즉 P과 A사이의 거리가 2고 마찬가지로 B, C와도 각각의 거리가 2라면 고를 수 있는 경우가 6이기 때문이죠)

같은 길이를 가진 점이 2개인 경우는 2 밖에 없으니까 2를 리턴했구요.