[leetCode/JS] 587. Erect the Fence

문제 설명

You are given an array trees where trees[i] = [xi, yi] represents the location of a tree in the garden.

You are asked to fence the entire garden using the minimum length of rope as it is expensive. The garden is well fenced only if all the trees are enclosed.

Return the coordinates of trees that are exactly located on the fence perimeter.

 

입출력 예

Example 1:

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

 

Example 2:

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

Constraints

• 1 <= points.length <= 3000
• points[i].length == 2
• 0 <= xi, yi <= 100
• All the given points are unique.

---

솔루션

• 좌표의 합으로 min, max를 구해서 정답을 도출했지만 예제1의 [4,2], [3,3], [2,4] 같이 같은 선상에 있는 점들을 찾을 수 없어서 결국 못풀었다.
• 서칭해보니 3개의 점을 받아서 각도 180도가 넘지 않는 점들을 감싸는 알고리즘이 필요했다.
• 자세한 해석을 보니 음.. 대수학이 필요했다. 쥐엔장 괜히 Hard가 아니구나!
• 알고리즘
• 알고리즘 GIF
• leetCode해석

const outerTrees = (trees) => {
    trees.sort((x, y) => {
        if (x[0] == y[0]) return x[1] - y[1];
        return x[0] - y[0];
    });
    let lower = [], upper = [];
    for (const tree of trees) {
        while (lower.length >= 2 && cmp(lower[lower.length - 2], lower[lower.length - 1], tree) > 0) lower.pop();
        while (upper.length >= 2 && cmp(upper[upper.length - 2], upper[upper.length - 1], tree) < 0) upper.pop();
        lower.push(tree);
        upper.push(tree);

    }
    return [...new Set(lower.concat(upper))];
};

const cmp = (p1, p2, p3) => {
    let [x1, y1] = p1;
    let [x2, y2] = p2;
    let [x3, y3] = p3;
    return (y3 - y2) * (x2 - x1) - (y2 - y1) * (x3 - x2);
};

감상평

• 어렵따!
• easy 문제를 하나 풀어서 머리를 식히고 랜덤 돌려야겠다.