On a plane there are n
points with integer coordinates points[i] = [xi, yi]
. Your task is to find the minimum time in seconds to visit all points.
You can move according to the next rules:
Input: points = [[1,1],[3,4],[-1,0]]
Output: 7
Explanation: One optimal path is [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]
Time from [1,1] to [3,4] = 3 seconds
Time from [3,4] to [-1,0] = 4 seconds
Total time = 7 seconds
Input: points = [[3,2],[-2,2]]
Output: 5
면 위에 n개의 점이 존재하머 각 점은 integer 좌표 points[i] = [xi, yi]
로 이루어져 있다.
모든 점을 지나는 최소한의 시간(초)를 구하라.
다음 규칙에 의해 점을 이동시켜야 한다.
// 시작점과 두번째점 사이의 x축과 y축의 차이를 구한다.
// dx == dy
// 절대값을 초에 더한다.
// dx != dy
// 두 수 중 적은 수만큼 대각선으로 가고, 큰 수에서 적은 수를 뺀 만큼 더 수평/수직으로 가므로
// 결과적으로 큰 수 만큼 초가 지난다.
// 메모
// 중요한건 절대값인가
// 방향은 중요하지 않은가 크기만 중요한가
// 둘 중에 더 적은 값만큼 대각선으로 진행한다.
// 0보다 큰 게 존재하면 그 만큼 또 진행하게 될 것이다.
// 가정해보자.
// 첫-둘 : 2,3 : 2초 + 1초 => 3초
// 첫-둘 : 4,4 : 4초 => 7초
// 점의 갯수는 임의이다.
// 마지막 점까지 실행
// range로 처리
func minTimeToVisitAllPoints(points [][]int) int {
seconds := 0
for i, _ := range points {
if i == len(points) - 1 {
return seconds
}
dx := points[i+1][0] - points[i][0]
dy := points[i+1][1] - points[i][1]
dx = int(math.Abs(float64(dx)))
dy = int(math.Abs(float64(dy)))
// 두 값이 같으면 절대값을 더한다.
if dx == dy {
seconds += int(math.Abs(float64(dx)))
} else {
// 큰 값의 절대값을 더한다.
if dx < dy {
seconds += int(math.Abs(float64(dy)))
} else {
seconds += int(math.Abs(float64(dx)))
}
}
}
return seconds
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
func optimalPath(a, b []int) int {
return max(abs(a[0] - b[0]), abs(a[1] - b[1]))
}
func minTimeToVisitAllPoints(points [][]int) int {
minTime := 0
for i := 0; i < len(points) - 1; i++ {
minTime += optimalPath(points[i], points[i+1])
}
return minTime
}
접근법은 대부분 비슷했다.
이 유저는 절대값을 구하는 함수를 구현하는 등 참고할만한 내용이 있어서 가져왔다.