Minimum Absolute Difference in an Array

하나의 array에서 원소중에 최소거리를 찾는 문제이다. 간단하지만 time complexity에 대해 생각해볼 필요가 있는 문제이다.

Problem

The absolute difference is the positive difference between two values $a$ and $b$, is written $\lvert a - b \rvert$ or $\lvert b - a \rvert$ and they are equal. If $a=3$ and $b=2$, $\lvert 3 - 2 \rvert = \lvert 2 - 3 \rvert = 1$. Given an array of integers, find the minimum absolute difference between any two elements in the array.

Array하나를 입력으로 받고 array 내의 원소중에 가장 가까운 거리 값을 return하는 함수를 작성하면 된다.

Answer

1
2
3
4
5
6
7
8

def minimumAbsoluteDifference(arr):
    sorted_arr = sorted(arr, reverse=True)
    min_dis = abs(sorted_arr[0] - sorted_arr[1])
    for i in range(len(sorted_arr) - 1):
        dist = abs(sorted_arr[i] - sorted_arr[i+1])
        if dist < min_dis:
            min_dis = dist
    return min_dis

Explanation

문제를 보자마자 가장 먼저 떠오른 것은 사실 반복문을 중첩시켜서 최소거리를 찾는 것이었다. Outer loop에서는 기준이 되는 수를 잡고 inner loop에서는 기준으로 잡은 수로부터의 거리를 모두 계산하면서 최소를 찾는 방식으로 bubble sort와 비슷하게 접근하는 것이었다.

이렇게 하면 찾을 수야 있지만 역시나 복잡도가 커서 모든 test를 통과하지 못했다. 이런 방식으로 접근하면 $O(n^2)$이므로 분명 바람직한 접근방법은 아니다.

더 나은 방법은 주어진 array를 sorting하고 sorted array의 처음부터 끝까지 각 간격을 측정하는 것이다. 이렇게 접근하면 sorting에 $O(n \log n)$을 사용하고 처음부터 끝까지 array sweep에 $O(n)$이 사용되어 총 $O(n \log n ) + O(n) = O(n \log n)$이 된다. 즉, $O(n^2)$보다 훨씬 적은 복잡도를 갖게 된다. (참고로 Python의 sorted는 Timsort를 사용하며 worst-case performance는 $O(n \log n)$이다)

Thanks to

• John Choi께서 Big O notation의 축약표현에 대해 코멘트 주셔서 간결하게 표현할 수 있었습니다. 🙇‍♂️

Reference

• HackerRank
• Timsort