1주차 | 문제 3. 최장 맨해튼 거리
문제
맨해튼 거리는 두 위치를 좌표로 나타내었을 때, 각각의 좌표의 차이에 따른 거리를 측정하는 방법이다.
(x1,y1), (x2,y2) 와 같이 좌표가 있을 때, 맨해튼 거리는 |x1-x2|+|y1-y2| 이다.
4개의 정수를 2개씩 짝을 지어 좌표로 표현한다고 할 때, 최장 맨해튼 거리를 찾는 프로그램을 출력하시오.(단, |x| 의 의미는 x가 음수일 때 -x를 반환하고, x가 양수일 때 x를 반환한다.)
입력
첫째 줄에 정수 4개가 공백을 두고 주어진다. 모든 정수는 -10,000 이상 10,000 이하의 정수이다. 단, 주어지는 모든 정수는 서로 다른 값이다.
출력
4개의 정수로 만들 수 있는 최장 맨해튼 거리를 찾고, 출력하시오.
풀이
import itertools
num=list(map(int,input().split())) # 4개의 정수를 입력받아 num이라는 리스트에 정수형으로 저장
case=list(itertools.permutations(num, 2)) # num에서 순서를 고려하여 2개를 선택하는 경우의 수(nP2)
distance=[] # 거리를 저장할 리스트
for i in range(len(case)): # case의 길이만큼 반복
point=set(num)-set(case[i]) # num에서 case[i]를 뺀 나머지 2개의 정수를 point라고 함
x=list(point)[0]-case[i][0]
y=list(point)[1]-case[i][1]
distance.append(x+y)
print(max(distance)) # 최장 거리 = 맨해튼 거리4개의 정수를 2개씩 짝을 지어야 한다는 부분이 가장 어렵게 다가왔다. 어떻게 하면 랜덤으로 4개의 정수 중에서 2개를 선택할 수 있을 지 고민하다보니 어려운 풀이가 된 것 같다.
단순히 4개 중 2개 선택이라고 하면 조합을 생각하게 되는데, 이 경우에는 x,y 좌표 값이라는 순서가 존재하므로 순열로 접근해야 했다. 그러다 보니 경우의 수가 많아졌고, 그만큼 for문도 많이 반복하게 된다.
구름 정답 코드
import sys
input = sys.stdin.readline
arr = list(map(int, input().split()))
arr.sort()
x = abs(arr[0] - arr[3])
y = abs(arr[1] - arr[2])
print(x + y)
입력받은 4개의 정수를 크기 순으로 정렬한 후 순서대로 a, b, c, d라고 하면, a < a + b < a + c < a + d와 같은 부등식이 성립한다.
공통적인 a를 제거하면 0 < b < c < d 와 같은 부등식이 항상 성립하게 되는데, 이 4개의 수(0, b, c, d)를 조합하여 각각의 맨해튼 거리를 구해보면 (b - 0) + (d - c), (c - 0) + (d - b), (d - 0) + (c - b)로 정리된다.
이 세 맨해튼 거리의 대소 비교를 하면 (b - 0) + (d - c) < (c - 0) + (d - b) = (d - 0) + (c - b) 와 같다.
우리는 최장 맨해튼 거리를 구해야 하므로 (c - 0) + (d - b), (d - 0) + (c - b) 경우의 좌표를 생각해보면 (a, a + b), (a + c, a + d) 또는 (a, a + b), (a + d, a + c)를 가질 때이다. 이 두 경우에 맨해튼 거리는 c + d - b가 된다.
따라서, 입력받은 4개의 정수를 크기 순으로 정렬한 뒤, (a, a + b), (a + c, a + d) 또는 (a, a + b), (a + d, a + c) 좌표를 가질 때의 맨해튼 거리를 구하면 최장일 때의 값을 구할 수 있게 된다.
구름 풀이를 참고하여 이해한대로 정리하였습니다.