Minimum Absolute Difference in an Array

생각했던 것

절대값들 중 최소값을 찾는 문제로, 모든 경우의 수를 비교하여 최소값을 찾아내면 된다.

진행

... 라고 하였으나 그러면 0(n^2) 시간에 끝날 것이기 때문에 비효율적이다. 경우의 수를 줄이기 위해서 생각한 것은 "정렬"이다. 예를 들어 오름차순으로 정렬했을때 [A, B, C] 배열이 도출되었다면 (A, B)의 차이는 (A, C)의 차이보다 작을 수 밖에 없다. 그러므로 모든 경우의 수를 따지지 않고, 바로 옆의 수와 비교하기만 하면 된다. 그러면 정렬하는 시간 O(nlogn) + 탐색시간 O(n)으로 O(nlogn) 시간 안에 끝낼 수 있다.

여담

각 수가 양수, 음수 여부에 따라 절대값 계산이 다를거라고 잠깐 착각했었다.. 그냥 뒷수에서 앞 수를 빼면 된다.

 

문제 조건에서 숫자 범위가 10억까지이므로 min의 초기화 값을 21억으로 주었다.