[LEETCODE] 1779.Find Nearest Point That Has the Same X or Y Coordinate

https://leetcode.com/

TITLE : 1779.Find Nearest Point That Has the Same X or Y Coordinate

Description : You are given two integers,xandy, which represent your current location on a Cartesian grid:(x, y). You are also given an arraypointswhere eachpoints[i] = [ai, bi]represents that a point exists at(ai, bi). A point isvalidif it shares the same x-coordinate or the same y-coordinate as your location.

Return the index (0-indexed) of the valid point with the smallest Manhattan distance from your current location. If there are multiple, return the valid point with the smallest index. If there are no valid points, return -1.

The Manhattan distance between two points (x1, y1) and (x2, y2) is abs(x1 - x2) + abs(y1 - y2).

 

  입력 좌표 x,y 에 대해서, points 에 저장된 좌표들이 유효하면 Manhattan distance(l1 - norm) 을 계산하는데, 최소 Manhattan distance 를 가지는 좌표의 인덱스(0-indexed)를 반환하면 된다. (유효한 좌표가 없는 경우에는 -1 을 반환.)

 

  이를 풀기 위해서 처음에는 pair<int, int> // {   distance,  index  } 를 element 로 가지는 1-d vector 을 선언해서, 유효한 좌표라면 distance 와 index 를 push_back 해주고, 그 vector 을 distance 기준으로 정렬한 뒤에 v[0].second 를 반환하면 될 것이라고 생각해서 구현하려고 했으나, 굳이 vector 을 불필요하게 더 선언해주지 않아도 가능하다는 것을 느꼈다. points 배열을 순환하며 각 좌표의 유효성을 검사한 뒤, 유효한 좌표에 대해서 distance 값을 계산하고 maxi 와 비교해서 더 작다면 maxi 를 distance 값으로 치환하고 ans 에 인덱스값을 저장하여 풀이할 수 있다.

 

( 다시 보니까 maxi 는 최소 거리를 저장하는 역할인데 maxi 라는 이름으로 지어준 거는 잘못된 것 같다. 시험기간이라 정신이 없나보다... mini 와 같이 이름을 지어주는 게 옳겠다. ) 

 

[C++]

class Solution {
public:
    int nearestValidPoint(int x, int y, vector<vector<int>>& points) {
        int dist = 0; int ans = -1; int maxi = INT_MAX;
        for (int i = 0; i < points.size(); i++) {
            if (x == points[i][0] || y == points[i][1]) {
                dist = abs(x - points[i][0]) + abs(y - points[i][1]);
                if (dist < maxi) {
                    maxi = dist;
                    ans = i;
                }
            }
        }
        return ans;
    }
};

시간복잡도 : O(N)