def set_min(target, A):
min_dist = float("inf")
for i, p in enumerate(A):
distance = dist(target, p)
if min_dist > distance:
min_dist = distance
A[0], A[i] = A[i], A[0]
return
def ClosestXdestinations(numDestinations, allocations, numDeliveries):
allocations.sort(key=lambda p: dist([0, 0], p))
allocations = [p for i, p in enumerate(allocations) if i < numDeliveries]
results = []
while allocations:
target = allocations.pop(0)
results.append(target)
allocations.sort(key=lambda p: dist(target, p))
set_min(target, allocations)
for x, y in results:
print(x, y)
return results
* 문제 풀이 2
- 한붓 그리기 형태 : 가장 끝에 점을 찾고 sorting하여 찾는 방법
- x로 sort / 동일 x 내에서 y로 sort
from collections import defaultdict
def Close(NumDes, allocations, numDeli):
spots = sorted(allocations, key=lambda xy: xy[0] 2 + xy[1] 2)[:numDeli]
x_y = defaultdict(list)
result = []
for x, y in spots:
x_y[x].append(y)
for x, y_list in x_y.items():
sorted_y = sorted(y_list)
for y in sorted_y:
result.append([x, y])
sorted_spots = sorted(result, key=lambda xy: xy[0])
first = sorted_spots[0]
last = sorted_spots[-1]
if first[0] ** 2 + first[1] ** 2 < last[0] ** 2 + last[1] ** 2:
return sorted_spots
else:
sorted_spots.reverse()
return sorted_spots
def dist(a, b): return sqrt((a[0] - b[0]) 2 + (a[1] - b[1]) 2)
def set_min(target, A): min_dist = float("inf") for i, p in enumerate(A): distance = dist(target, p) if min_dist > distance: min_dist = distance A[0], A[i] = A[i], A[0] return
def ClosestXdestinations(numDestinations, allocations, numDeliveries): allocations.sort(key=lambda p: dist([0, 0], p)) allocations = [p for i, p in enumerate(allocations) if i < numDeliveries] results = [] while allocations: target = allocations.pop(0) results.append(target)
allocations.sort(key=lambda p: dist(target, p))
from collections import defaultdict
def Close(NumDes, allocations, numDeli): spots = sorted(allocations, key=lambda xy: xy[0] 2 + xy[1] 2)[:numDeli] x_y = defaultdict(list) result = [] for x, y in spots: x_y[x].append(y) for x, y_list in x_y.items(): sorted_y = sorted(y_list) for y in sorted_y: result.append([x, y]) sorted_spots = sorted(result, key=lambda xy: xy[0])
~