[Python] 2381번 최대 거리

2381번: 최대 거리 (acmicpc.net)

2381번: 최대 거리

---

 

22/09/03

 

 

그룹 연습에서 풀었던 문제이다. 이 문제는 애드혹 태그에 속하는데, 발상이 골드 3에 걸맞은 발상이라고 생각한다.

 

나 같은 경우 이 문제의 해답의 일부분을 어딘가에서 봤던 기억이 났기 때문에 풀 수 있었다.

---

 

문제 접근 방식:

 

이 문제의 시간제한은 1초이고, 파이썬 시간제한을 기준으로 하면 3초인데, 만약 그냥 두 점을 비교하는 방식으로 푼다면 입력의 크기가 50000*50000 = 25억이기 때문에 절대로 시간 내에 풀지 못한다.

 

따라서 시간 복잡도가 O(n^2)보다 더 작은 알고리즘을 택하여 골라야 한다.

 

이 알고리즘을 떠올리는 것이 매우 어렵다.

 

가능한 케이스들

가능한 케이스들을 모두 나열하면 다음과 같은데, 자세히 관찰해보면 항상 합과 차의 차이끼리로만 이루어져 있다는 사실을 알 수 있다.

 

1번과 4번 케이스를 보면, 각 점의 (x좌표 + y좌표)끼리의 차를 나타낸 것이고, 2번과 3번 케이스를 보면 각 점의 (x좌표 - y좌표)끼리의 차를 나타낸 것이다.

 

따라서 만약 1번과 4번에서 최댓값이 나온다면 각 점마다 (x좌표 + y좌표)를 구하여 리스트를 만든 다음에, 그 리스트의 최댓값 - 최솟값을 구해주면 된다.

 

만약 2번과 3번에서 최댓값이 나온다면 마찬가지로 각 점마다 (x좌표 - y좌표)를 구하여 리스트를 만든 다음, 그 리스트의 최댓값 - 최솟값을 구해주면 된다.

 

이 방식은 각 리스트 별 최댓값과 최솟값만 구하면 되므로, O(n)의 시간 복잡도를 가진다. 따라서 시간제한에 충분히 들어갈 수 있는 방식이다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 2381번 최대 거리
# 수학, 정렬, 애드 혹
import sys
input = sys.stdin.readline

N = int(input())
points = list(tuple(map(int, input().rstrip().split())) for _ in range(N))
sorted_1 = sorted(points, key = lambda p: p[0]+p[1])
sorted_2 = sorted(points, key = lambda p: p[0]-p[1])
max_d = max(abs(sorted_1[0][0]-sorted_1[-1][0]) + abs(sorted_1[0][1]-sorted_1[-1][1]), abs(sorted_2[0][0]-sorted_2[-1][0]) + abs(sorted_2[0][1]-sorted_2[-1][1]))
print(max_d)