문제: https://app.codility.com/programmers/lessons/15-caterpillar_method/min_abs_sum_of_two/start/
풀이: 문제를 쉽게 해석해 보자면 두 인자의 절대 값 차이 중 가장 작은 값을 구하는 것이다. 그래서 인자의 절대 값 기준으로 정렬 후 계산 하는 것이 효율적일 것이라 생각했다. 정렬 후엔 붙어 있는 인자끼리 절대 값의 차이가 가장 작게 되니 붙어 있는 인자끼리만 비교해보면 된다. (0, 0)과 같이 같은 index의 인자로 pair를 구성할 수도 있으므로 절대 값이 가장 작은 숫자의 2배수 값으로 시작하여 최소 값을 찾았다. 다른 중복된 인자로 구성 된 pair는 무조건 이보다 클 수 밖에 없으므로 체크하지 않아도 된다.
def solution(A):
A.sort(key=lambda x: abs(x)) # 인자의 절대 값 기준으로 정렬
minimum = abs(A[0] + A[0]) # 중복된 인자로 구성 된 pair는 가장 작은 인자로만 체크하면 된다
for i in range(len(A) - 1):
# 정렬을 했기 때문에 서로 붙어있는 인자가 절대 값의 차이가 가장 작을 수 밖에 없다
minimum = min(minimum, abs(A[i] + A[i + 1]))
return minimum시간 복잡도는 O(N*log(N))
끄적