1637. Widest Vertical Area Between Two Points Containing No Points

#Array #Sorting

 

n개의 점이 2D 평면에 points[i] = [xi, yi] 으로 주어진다.

영역 안에 다른 점이 없는 가장 넓은 수직영역을 반환하라.

 

수직영역은 너비가 고정된, Y축을 따라 무한하게 확장하는 영역이다.

가장 넓은 수직영역은 가장 긴 너비를 가진 영역이다.

 

영역의 모서리 위의 점은 영역에 포함되지 않는다.

 

---

Trial 1 : Python3, 22/02/11

class Solution:
    def maxWidthOfVerticalArea(self, points: List[List[int]]) -> int:
        points.sort()
        re=0
        for i in range(1,len(points)):
            re = max(re, points[i][0]-points[i-1][0])
        return re

풀이:

내부에 다른 점이 없어야 하고, 모서리 위의 점은 신경쓰지 않으며, 가로의 길이로 영역 넓이가 결정된다.

따라서 points[] 배열의 점들 중 x 좌표만 이용하면 된다.

먼저, points[] 배열을 x 좌표를 기준으로 정렬한다. 파이썬에서는 sort() 메소드를 이용하면 각 요소의 0번째 인덱스로 정렬하므로 x 좌표를 기준으로 배열을 쉽게 정렬할 수 있다.

또한 중간에 포함되는 점이 없어야 하므로 한단계씩의 가로 길이를 측정하고 가장 긴 가로가 곧 반환값이 된다.

따라서 for 반복문을 통해 각 점의 가로 길이를 측정하고 가장 큰 값을 갱신해서 반환한다.

 

 

리뷰: 

런타임은 46.82%, 메모리는 57.63% 의 결과를 얻었다.

파이썬으로 해결한 방법은 간단했지만 다른 언어로 푸는 경우에 시간과 공간을 더 아낄 수 있는 것 같다.