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

1. Input

1) int x

2) int y

3) int[][] points

 

2. Output

1) 다음 조건을 만족한 points의 점의 인덱스를 반환

- (x,y)와 x좌표 또는 y좌표가 같아야 한다.

- 멘하탄 거리가 가장 짧아야 한다.

- 멘하탄 거리는 |x2-x1| + |y2-y1|으로 계산한다.

- 조건을 만족하는 점이 여러개라면 points에서의 인덱스가 가장 작은 것을 반환한다.

2) 조건을 만족하는 점이 없다면 -1을 반환

 

3. Constraint

1) 1 <= points.length <= 10^4

2) points[i].length == 2

3) 1 <= x, y, ai, bi <= 10^4

 

4. Example

Input: x = 3, y = 4, points = [[1,2],[3,1],[2,4],[2,3],[4,4]] -> Output: 2

설명: (3,4)와 x좌표 또는 y좌표가 같은 점은 3개가 있다.

- [3.1]: d = |3-3| + |4-1| = 3

- [2,4]: d = |3-2| + |4-4| = 1

- [4,4]: d = |3-4| + |4-4| = 1

- 멘하탄 거리가 가장 짧은 점이 2개이고, 이 두 점의 points에서 인덱스는 2, 4이다. 따라서 둘 중 더 작은 2를 반환한다.

 

5. Code

1) 첫 코드(2023/06/20)

class Solution {
    public int nearestValidPoint(int x, int y, int[][] points) {
        HashMap<Integer, Integer> m = new HashMap<>();
        // m: index, distance
        int min = Integer.MAX_VALUE;
        for(int i=0 ; i<points.length ; i++){
            if(points[i][0]==x || points[i][1]==y){
                m.put(i, Math.abs(points[i][0]-x) + Math.abs(points[i][1]-y));
                if(m.get(i)<min)
                    min = m.get(i);
            }
        }
        if(m.size()==0)
            return -1;
        
        int index = points.length;
        for(int i : m.keySet()){
            if(m.get(i)==min){
                if(i<index)
                    index = i;
            }
        }

        return index;
    }
}

- 82%, 21%

 

2) 약간만 수정해본 코드(2023/06/20)

class Solution {
    public int nearestValidPoint(int x, int y, int[][] points) {
        HashMap<Integer, Integer> m = new HashMap<>();
        // m: index, distance
        int min = Integer.MAX_VALUE;
        for(int i=0 ; i<points.length ; i++){
            if(points[i][0]==x){
                m.put(i, Math.abs(points[i][1]-y));
                if(m.get(i)<min)
                    min = m.get(i);
            } else if(points[i][1]==y){
                m.put(i, Math.abs(points[i][0]-x));
                if(m.get(i)<min)
                    min = m.get(i);
            }
        }
        if(m.size()==0)
            return -1;
        
        int index = points.length;
        for(int i : m.keySet()){
            if(m.get(i)==min){
                if(i<index)
                    index = i;
            }
        }

        return index;
    }
}

- 82%, 37%

- 코드가 조금 길어진 대신 메모리 사용량이 줄었다.