[구름 알고리즘 먼데이 챌린지] 1주차 | 문제3 최장 맨해튼 거리 | 파이썬

2022. 10. 12. 00:41·Algorithm/구름 알고리즘 먼데이 챌린지

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) 좌표를 가질 때의 맨해튼 거리를 구하면 최장일 때의 값을 구할 수 있게 된다.

구름 풀이를 참고하여 이해한대로 정리하였습니다.

저작자표시 (새창열림)
'Algorithm/구름 알고리즘 먼데이 챌린지' 카테고리의 다른 글
  • [구름 알고리즘 먼데이 챌린지] 2주차 | 문제1 합격자 찾기 | 파이썬
  • [구름 알고리즘 먼데이 챌린지] 1주차 | 문제4 소수 찾기 | 파이썬
  • [구름 알고리즘 먼데이 챌린지] 1주차 | 문제2 동명이인 | 파이썬
  • [구름 알고리즘 먼데이 챌린지] 1주차 | 문제1 경로의 개수 | 파이썬
dduniverse
dduniverse
  • dduniverse
    dduniverse
    dduniverse
  • 전체
    오늘
    어제
    • 분류 전체보기 (245)
      • Algorithm (123)
        • 알고리즘 이론 (8)
        • 백준 (19)
        • 프로그래머스 (83)
        • 구름 알고리즘 먼데이 챌린지 (13)
      • 빅데이터분석기사 (10)
        • 통계 (4)
        • 실기 (6)
      • KT에이블스쿨 (26)
      • FrontEnd (11)
        • React (5)
        • 기타 (6)
      • BackEnd (18)
        • Django (15)
        • Spring (3)
      • DS & ML (11)
        • Machine Learning (9)
        • Kaggle (2)
      • TIL (46)
        • python (22)
        • javascript (3)
        • 오류해결 (10)
        • 기타 (10)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
    • 관리
    • 글쓰기
  • 링크

  • 인기 글

  • hELLO· Designed By정상우.v4.10.0
dduniverse
[구름 알고리즘 먼데이 챌린지] 1주차 | 문제3 최장 맨해튼 거리 | 파이썬
상단으로

티스토리툴바