[LeetCode] 447. Number of Boomerangs

문제 출처: https://leetcode.com/problems/number-of-boomerangs/

Number of Boomerangs - LeetCode

문제

평면에서 n개의 구분되어지는 points가 주어진다(points[i] = [xi, yi]). 부메랑은 i와 j사이의 거리와 i와 k 사이의 거리가 같은 점 (i, j, k)의 튜플입니다.(튜플의 순서가 중요)

 

부메랑의 수 를 반환하라.

예제

Input: points = [[0,0],[1,0],[2,0]]
Output: 2

Explanation: The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]].

Input: points = [[1,1]]
Output: 0

풀이

어떤 한 지점 i와 d만큼의 거리를 갖는 지점이 num개 있다고 하면, 문제에서 요구하는 부메랑을 만드는 케이스는 num * (num-1)개 이다.

 

바로 이점을 이용하여 문제를 풀어보자.

1. 거리 계산의 기준이 될 i를 선택한다.(points 배열의 모든 점이 기준으로 선정되어야 한다.)
2. 기준이 된 점을 제외하고 나머지 점에 대해서 i와의 거리를 계산한다.
3. 거리 별로 개수를 카운팅 한다.
4. 기준 점과 다른 모든 점들과의 거리 계산이 완료된 후, 거리 별로 돌면서 부메랑의 수를 계산한다.

var numberOfBoomerangs = function(points) {
    let ans = 0;

    for (let i = 0; i < points.length; i++) {
        // 기준 지점 설정
        const [x, y] = points[i];
        const dist = new Map();

        // 기준 지점과의 거리 계산
        for (let j = 0; j < points.length; j++) {
            if (i === j) { continue; }

            const d = Math.sqrt(Math.pow((x-points[j][0]), 2) + Math.pow((y-points[j][1]), 2));
            if (!dist.has(d)) { dist.set(d, 0); }
            dist.set(d, dist.get(d) + 1);
        }

        // 부메랑 수 계산
        for (let val of dist.values()) {
            if (val < 1) { continue; }

            ans += val * (val-1);
        }
    }

    return ans;
};

Github: 447.js

opwe37/Algorithm-Study