[golang] LeetCode #1266. Minimum Time Visiting All Points

1. 문제

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:

• In one second always you can either move vertically, horizontally by one unit or diagonally (it means to move one unit vertically and one unit horizontally in one second).
• You have to visit the points in the same order as they appear in the array.

Example 1:

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

Example 2:

Input: points = [[3,2],[-2,2]]
Output: 5

Constraints:

• points.length == n
• 1 <= n <= 100
• points[i].length == 2
• -1000 <= points[i][0], points[i][1] <= 1000

해설

면 위에 n개의 점이 존재하머 각 점은 integer 좌표 points[i] = [xi, yi] 로 이루어져 있다.
모든 점을 지나는 최소한의 시간(초)를 구하라.

다음 규칙에 의해 점을 이동시켜야 한다.

• 수직, 수평, 대각선으로 한 단위 이동하는 것은 모두 1초이다.
• 배열에 표현되어 있는 순서대로 진행해야한다.

2. 접근

// 시작점과 두번째점 사이의 x축과 y축의 차이를 구한다.

// dx == dy 
// 절대값을 초에 더한다.

// dx != dy 
// 두 수 중 적은 수만큼 대각선으로 가고, 큰 수에서 적은 수를 뺀 만큼 더 수평/수직으로 가므로
// 결과적으로 큰 수 만큼 초가 지난다.

// 메모
// 중요한건 절대값인가
// 방향은 중요하지 않은가 크기만 중요한가
// 둘 중에 더 적은 값만큼 대각선으로 진행한다.
// 0보다 큰 게 존재하면 그 만큼 또 진행하게 될 것이다. 
// 가정해보자.
// 첫-둘 : 2,3 : 2초 + 1초 => 3초 
// 첫-둘 : 4,4 : 4초 => 7초

// 점의 갯수는 임의이다. 
// 마지막 점까지 실행
// range로 처리

3. 내가 작성한 답

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
}

4. 다른 유저의 답안

1. 함수를 만드는 유저

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
}

접근법은 대부분 비슷했다.
이 유저는 절대값을 구하는 함수를 구현하는 등 참고할만한 내용이 있어서 가져왔다.

5. 추가로 공부한 내용

6. 참고사이트