[LeetCode-1266] Minimum Time Visiting All Points

https://leetcode.com/problems/minimum-time-visiting-all-points/

Minimum Time Visiting All Points - LeetCode

---

[ 코드1 -풀이]

(1) 만약에 points의 개수가 0개거나, 1개면 => 더이상 이동할 필요없으므로 0을 리턴

(2) points의 개수가 2개이상인 경우

시작점 0,1, 2, ..., len(points)-2

도착점 1,2,3, ...., len(points)-1

 

시작점의 좌표를 (starty, startx), 도착점의 좌표를 (endy, endx) 라 하면

x 좌표값 차이를 dx라 하면, dx= endx- startx

y좌표값 차이를 dy라 하면,  dy= endy- starty

 

dx와 dy의 절댓값중 가장 작은 값을 골라서.

작은 값만큼 대각선으로 이동한다.

 

예를 들어, 시작점은 (1,1), 도착점을 (3,4)라하면

dx=2, dy=3이다.

즉, dx가 dy보다 절대값이 작으므로, 2번을 대각선으로 이동한다.

 

대각선 이동은 4가지가 존재한다.

(1) dx>0, dy>0

대각선 이동 전 좌표: (x,y)

대각선 이동 후 좌표: (x+1, y+1)

 

(2) dx>0, dy<0

대각선 이동 전 좌표: (x,y)

대각선 이동 후 좌표: (x+1, y-1)

 

(3) dx<0, dy>0

대각선 이동 전 좌표: (x,y)

대각선 이동 후 좌표: (x-1, y+1)

 

(4) dx<0, dy<0

대각선 이동 전 좌표: (x,y)

대각선 이동 후 좌표: (x-1, y-1)

 

 

위를 참고하여 다시 예시를 적용하면,

 

시작점이 (1,1)이고 도착점이 (3,4)일때 dx=2, dy=3이므로,

2번의 대각선이동(dx>0, dy>0) 을 하게되고

나머지 1번의 y축 이동을 한다.

 

그다음 시작점이 (3,4)이고 도착점이(-1,0)일때 dx=-4, dy=-4 이므로

4번의 대각선이동 (dx<0, dy<0)을 하게된다.

 

조금 무식한 방법으로 풀었으나

쓸데없는 코드가 많기도하고 시간이 오래걸렸다. 

이 코드의 시간복잡도는 O(N**2)이다.

---

[ 코드1 ]

class Solution:
	def __init__(self):
    	self.cnt=0
        
	def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
    	#점이 한개거나, 없는경우
        if len(points)<=1:
            return 0
       
        #시작점
        for i in range(len(points)-1):
            startx, starty =points[i]    #시작점
            endx, endy =points[i+1]  #도착점
            
            diffx= endx-startx
            diffy= endy-starty
            
            cross_cnt=min(abs(diffx), abs(diffy))
            
            #대각선으로 이동
            for i in range(cross_cnt):
                #x좌표 이동
                if diffx>0:
                    startx+=1
                    diffx-=1
                    
                elif diffx<0:
                    startx-=1
                    diffx+=1
                
                #y좌표 이동
                if diffy>0:
                    starty+=1
                    diffy-=1
                    
                elif diffy<0:
                    starty-=1
                    diffy+=1
                    
                self.cnt+=1
            #만일 diffx가 0이 아니라면, 남은 횟수만큼 이동
            if abs(diffx)>0:
                for i in range(abs(diffx)):
                    if diffx>0:
                        startx+=1
                        diffx-=1
                    
                    elif diffx<0:
                        startx-=1
                        diffx+=1
                    self.cnt+=1
                        
                
            #만일 diffy가 0이 아니라면, 남은횟수만큼 이동
            elif abs(diffy)>0:
                for i in range(abs(diffy)):
                    if diffy>0:
                        starty+=1
                        diffy-=1
                    
                    elif diffy<0:
                        starty-=1
                        diffy+=1
                    self.cnt+=1
                        
        return self.cnt

---

[코드2]

그런데 O(N)으로도 풀 수 있다.

 

시작점과 도참점의 거리차인 dy, dx중 작은 값은

결국에는 대각선으로 이동한다는 것이고

그리고 dy, dx중 대각선으로 이동한 것을 뺀뒤에

dy, dx 가 0보다 크게되면 그 나머지 이동횟수를 더한다. 

어차피 dy,dx중 하나만 남게된다.

둘다 같으면 대각선으로 이동하게 되니까.

 

무슨말이냐면

시작점이 (3,2), 도착점이 (-2,4)라 하자

그러면 dx=-5, dy=2 이다.

 

dx와 dy의 절댓값 크기를 비교하여, 작은값이 대각선으로 이동한 횟수이다.

(굳이 방향과 좌표를 따질 필요가 없다는 것이다!)

 그러면 대각선으로 이동한횟수는 2번이다.

 

그러면 dx의 절댓값 5는 대각선으로 2번이동햇고, 앞으로 3번 이동해야

도착점에 도달할 수 있다.

class Solution:
    def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
        if len(points)<=1:
            return 0
        
        cnt=0
        for i in range(len(points)-1):
            start=points[i]
            end=points[i+1]
            
            dx=abs(end[0]-start[0])
            dy=abs(end[1]-start[1])
            
            #대각선이동: dy,dx중 작은값만큼 대각선으로 이동
            cross_shift=min(dy, dx)
            cnt+=cross_shift
            dx-=cross_shift
            dy-=cross_shift
            
            #나머지 이동
            if dx>0:
                cnt+=dx
            elif dy>0:
                cnt+=dy
        return cnt

시간이 1200ms에서 60ms로 20배나 줄였다!