파이썬으로 다른 점이 포함되지 않는 가장 넓은 수직 영역 구하기

문제 개요

n개의 점이 좌표 (x, y) 형태로 주어졌다고 가정해 봅시다. 여기서 수직 영역(vertical area)이란 y축 방향으로 무한히 뻗어 있는 영역을 의미합니다. 우리가 구해야 할 것은 두 점 사이에 존재하는 수직 영역 중, 그 내부에 어떤 점도 포함되지 않으면서 폭이 가장 넓은 영역입니다.

예를 들어 입력이 다음과 같다면,

pts = [[10,9],[11,11],[9,6],[11,9]]

출력 결과는 1이 됩니다.

아래 그림에서 빨간색과 파란색으로 표시된 영역이 최적의 답이며, 해당 영역 안에는 어떤 점도 존재하지 않습니다.

접근 방법

이 문제는 생각보다 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 수직 영역의 폭은 오직 x좌표의 차이로 결정되므로, y좌표는 고려할 필요가 없습니다.
• 먼저 점들의 목록인 pts를 정렬합니다.
• 정렬된 상태에서 인접한 두 점 사이의 x좌표 차이를 모두 계산합니다.
• 그 차이들 중 최댓값을 반환하면, 그것이 곧 다른 점을 포함하지 않는 가장 넓은 수직 영역의 폭입니다.

즉, 정렬 후 인접한 점들 사이의 x좌표 간격 중 가장 큰 값을 찾는 것이 전부입니다.

구현 예제

아래 파이썬 코드를 통해 더 자세히 이해해 보겠습니다.

def solve(pts):
   pts.sort()
   return max(pts[i][0] - pts[i - 1][0] for i in range(1, len(pts)))
print(solve([[10,9],[11,11],[9,6],[11,9]]))

입력

[[10,9],[11,11],[9,6],[11,9]]

출력

1

동작 원리 설명

주어진 점들을 x좌표 기준으로 정렬하면 [[9,6], [10,9], [11,11], [11,9]] 순서가 됩니다. 이때 인접한 점들 사이의 x좌표 차이는 각각 1, 1, 0입니다. 따라서 최댓값인 1이 정답이 됩니다.

이 알고리즘의 시간 복잡도는 정렬에 의해 지배되므로 O(n log n)이며, 공간 복잡도는 O(1)로 매우 효율적입니다.