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

문제

You are given two integers, x and y, which represent your current location on a Cartesian grid: (x, y). You are also given an array points where each points[i] = [ai, bi] represents that a point exists at (ai, bi). A point is valid if 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 좌표와 [x, y] 배열을 갖고 있는 2차원의 points 배열이 들어온다.

내가 있는 x나 y의 값이 같고, 나와 가장 가까이에 있는 좌표의 인덱스를 반환한다.

내가 있는 x나 y의 값이 같은 좌표가 하나도 없을 경우 -1을 반환한다.

거리가 같은 좌표가 여러 개 존재할 경우, 가장 낮은 인덱스를 반환한다.

 

예시

Example 1:

Input: x = 3, y = 4, points = [[1,2],[3,1],[2,4],[2,3],[4,4]]
Output: 2
Explanation: Of all the points, only [3,1], [2,4] and [4,4] are valid. Of the valid points, [2,4] and [4,4] have the smallest Manhattan distance from your current location, with a distance of 1. [2,4] has the smallest index, so return 2.

Example 2:

Input: x = 3, y = 4, points = [[3,4]]
Output: 0
Explanation: The answer is allowed to be on the same location as your current location.

Example 3:

Input: x = 3, y = 4, points = [[2,3]]
Output: -1
Explanation: There are no valid points.

 

제약조건

Constraints:

• 1 <= points.length <= 104
• points[i].length == 2
• 1 <= x, y, ai, bi <= 104

 

해결 과정

전체적으로 두 가지로 나누어 생각해보았다.

첫번째는 나와 같은 x, y에 존재하는 좌표들을 고른다.

두번째는 그 좌표들과 나의 거리를 비교하여 가장 가까운 좌표의 인덱스를 반환한다.

• 같은 x, y 상에 있는 좌표들을 담을 valid 배열을 선언한다.
• points를 전체 탐색한다.
  • 만약 나의 x값과 points[i]의 x값이 같거나, 나의 y값과 points[i]의 y값이 같을 때 valid 배열에 담긴다.
• 탐색이 끝나고 난 후, valid의 길이가 0이라면 내가 있는 x나 y의 값이 같은 좌표가 하나도 없을 경우이기 때문에 -1을 반환한다.
• 이제 거리를 비교할 차례다. 좌표들끼리 비교할 최단 거리를 초기화한다. 이때, 처음으로 비교를 할 경우 무조건 첫번째의 수가 담겨야 하기 때문에 정수 중 가장 큰 숫자를 할당한다. (지금 생각해보니 첫 인덱스의 값을 할당해도 괜찮을 방법이라고 생각한다.) 그리고 가장 가까이에 있는 좌표를 담을 minArr도 선언한다.
• valid를 전체 탐색한다.
  • 문제에 나와있는 distance를 구하는 식을 이용하여 dis 변수에 할당한다.
  • 이때 dis가 min보다 작을 경우, min에 dis 값을 넣어주고 minArr에도 현재의 좌표를 넣는다. 좌표값을 넣기 전에, 이전에 저장되었던 값들을 초기화시키기 위해 length를 0으로 만든다.
  • 만약 길이가 같을 경우, 아무런 동작을 수행하지 않고 넘어간다. 현재 minArr에 담겨있는 좌표가 인덱스 값이 더 작기 때문에 현재의 좌표값을 굳이 넣어줄 필요가 없다.
• 탐색이 끝나면 minArr[0] 값을 points 배열에서 찾아 인덱스 값을 반환한다.

 

해결 코드

/**
 * @param {number} x
 * @param {number} y
 * @param {number[][]} points
 * @return {number}
 */
var nearestValidPoint = function(x, y, points) {
    
    // 1. valid 확인
    let valid = [];
    
    for(let i = 0 ; i < points.length ; i++){
        if(points[i][0] === x || points[i][1] === y){
            valid.push(points[i]);
        }
    }
    if(valid.length === 0) return -1;
    
    // 2. 거리 비교
    let min = Number.MAX_SAFE_INTEGER;
    let minArr = [];
    
    for(let i = 0 ; i < valid.length ; i++){
        let dis = Math.abs(x - valid[i][0]) + Math.abs(y - valid[i][1]);        
        
        if(dis < min){
            min = dis;
            minArr.length = 0;
            minArr.push(valid[i]);
        }else if(dis === min){
            continue;
        }
    }
    
    return points.indexOf(minArr[0]);
    
};