⚡문제 유형
배열
📝문제
입력값으로 현재 좌표 위치인 X, Y와 좌표에 찍힌 점의 정보인 points가 온다.
사용자 위치와 동일한 x 좌표 또는 동일한 y 좌표를 공유하는 경우 유효한 point이다.
현재 위치에서 맨해튼 거리 가 가장 작은 유효한 지점 의 points를 반환하는 문제이다.
정답이 여러개면 인덱스 번호가 가장 작은 것을 반환하고 유효한 포인트가 없으면 -1를 반환한다.
두 점 사이의 맨해튼 거리는 (x1, y1)(x2, y2)abs(x1 - x2) + abs(y1 - y2)이다.
📘예시
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.
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.
Input: x = 3, y = 4, points = [[2,3]]
Output: -1
Explanation: There are no valid points.
📗풀이
1. points 중 x나 y랑 좌표가 같다면 유효한 지점이다.
2. 유효한 지점 중에서 최단 거리를 가진 좌표의 인덱스를 가져오기
아래 예시로 설명을 해보자. (x= 3, y=4)
[[1,2],[3,1],[2,4],[2,3],[4,4]]
배열에서 x = 3이거나 y = 4인 애들은 맨해튼 거리를 구하고 나머지는 무한대 값을 준다
[1,2] | [3,1] | [2,4] | [2,3] | [4,4] |
∞ | 3 | 1 | ∞ | 1 |
이 중 최소값 중 인덱스번호가 가장 작은 [2,4]의 인덱스 번호인 2가 정답이다.
만약, 모든 point값이 ∞인 경우에는 -1를 반환해주면 된다.
📕코드
둘다 같은 접근 방식이지만 첫번째 코드가 지저분해보여 forEach문을 사용해 다시 구현해봤다
var nearestValidPoint = function (x, y, points) {
let current = [x, y];
let distance = [];
for (let i = 0; i < points.length; i++) {
if (current[0] === points[i][0] || current[1] === points[i][1]) {
distance.push(
Math.abs(current[0] - points[i][0]) +
Math.abs(current[1] - points[i][1])
);
} else distance.push(Number.POSITIVE_INFINITY);
}
if (Math.min(...distance) === Number.POSITIVE_INFINITY) {
return -1;
} else {
return distance.indexOf(Math.min(...distance));
}
};
var nearestValidPoint = function (x, y, points) {
let index = -1;
let min = Number.POSITIVE_INFINITY;
points.forEach(([a, b], i) => {
if (a === x || b === y) {
const distance = Math.abs(x - a) + Math.abs(y - b);
if (distance < min) {
min = distance;
index = i;
}
}
});
return index;
};
'자료구조&알고리즘 > 알고리즘' 카테고리의 다른 글
[LeetCode][JS] 1502번 Can Make Arithmetic Progression From Sequence (0) | 2022.05.27 |
---|---|
[leetCode][JS] 1822번 Sign of the Product of an Array (0) | 2022.05.27 |
[LeetCode][JS] 1281번 Subtract the Product and Sum of Digits of an Integer (0) | 2022.05.26 |
[LeetCode][JS] 191번 Number of 1 Bits (0) | 2022.05.25 |
[LeetCode][JS] 231번 Power of Two (3) | 2022.05.24 |