주어진 값에서 가장 가까운 거리를 구하는 알고리즘

K Closest Points to the Origin And Given Value.py

# ref: https://www.youtube.com/watch?v=eaYX0Ee0Kcg&t=0s&list=PLBZBJbE_rGRVnpitdvpdY9952IsKMDuev&index=5
# 이 모듈의 기능
# 1. 주어진 좌표 배열에서 0, 0과 가장 가까운 값을 구한다.
# 2. 주어진 좌표 배열에서 주어진 좌표와 가장 가까운 값을 구한다.
# 3. 주어진 좌표 배열에서 주어진 좌표와 가장 가까운 값의 배열을 구한다.

# functions of this module
# 1. get closest points from 0, 0 in given points array
# 2. get closest points from given value in given points array
# 3. get closest points array from given value in given points array

# Vector 연산을 이용해 가까운 거리를 구한다.
# --get_from_zero(self) 함수 설명--
# 1. 각 튜플의 값을 가져온다.
# 2. 피타고라스 정리를 사용해 거리를 구한다.
# 3. 구한 거리에서 최소값을 가진 인덱스를 찾아낸다.
# 4. points에서 같은 인덱스 번호를 가진 값을 출력한다.

# --get_from_value(self, origin) 함수 설명--
#1. 각 튜플에서 백터 뺄셈을 한다.
#2. get_from_zero(self) 함수를 수행한다.

# get_several_from(self, origin, num) 함수 설명--
#1. 주어진 num 만큼 반복한다.
#2. self.points 배열을 pop해서 개수를 줄여준다.
#3. pop한 값을 저장해서 반복 끝나고 반환한다.
import math


class ClosestPoints:
    def __init__(self, points):
        self.points = points

    def get_from_zero(self):
        results = []

        if len(self.points) is 0:
            return []

        for i in self.points:
            results.append(math.sqrt(math.pow(i[0], 2) + math.pow(i[1], 2)))

        closest_point_index = results.index(min(results))

        return self.points[closest_point_index]

    def get_from(self, origin):
        subtracted_points = []
        points_temp = self.points

        try:
            for point in self.points:
                subtracted_points.append(self.subtract(origin, point))
            self.points = subtracted_points
            closest_point_index = self.points.index(self.get_from_zero())
        except IndexError:
            return ()
        except ValueError:
            return []
        else:
            self.points = points_temp
            return self.points[closest_point_index]

    def get_several_from(self, origin, num):
        results = []

        for i in range(num):
            if len(self.points) is 0:
                return results
            closest_point = self.get_from(origin)
            self.points.pop(self.points.index(closest_point))
            results.append(closest_point)
        return results

    def subtract(self, origin, point):
        sub = []

        for i in range(0, 1+1):
            sub.append(origin[i] - point[i])
        return tuple(sub)


assert ClosestPoints([(-2, 4), (-2, 3), (2, -1), (2, -4)]).get_from((2, -1)) == (2, -1)
assert ClosestPoints([(-2, 4), (-2, 3), (2, -1), (2, -4)]).get_from((2, 1)) == (2, -1)
assert ClosestPoints([(-2, 4), (-2, 3), (2, -4), (2, -2)]).get_from((2, 1)) == (2, -2)
assert ClosestPoints([(-2, 4), (-2, 3), (2, -4), (2, -3)]).get_from((-1, 3)) == (-2, 3)
assert ClosestPoints([]).get_from((-1, 3)) == []
assert ClosestPoints([(-2, 4), (-2, 3), (2, -4), (2, -3)]).get_from(()) == ()
assert ClosestPoints([(2, 1), (2, 2), (2, 0), (2, 3), (2, -1), (2, 4), (2, -2)]).get_several_from((2, 1), 7) == [(2, 1), (2, 2), (2, 0), (2, 3), (2, -1), (2, 4), (2, -2)]
assert ClosestPoints([(2, 1), (2, 2), (2, 0), (2, 3), (2, -1), (2, 4), (2, -2)]).get_several_from((2, 1), 0) == []
assert ClosestPoints([(2, 1), (2, 2), (2, 0), (2, 3), (2, -1), (2, 4), (2, -2)]).get_several_from((2, 1), 10000) == [(2, 1), (2, 2), (2, 0), (2, 3), (2, -1), (2, 4), (2, -2)]

TODO: heap으로 구현해보기