[파이썬][HackerRank] Minimum Absolute Difference in an Array . python 문제 풀이

1. 문제 이해

제목과 같다.

배열의 숫자 두개중에 절대차가 가장 작은거를 찾으면 된다.

2. 풀이 접근

3 -7 0

일때는 완전탐색 해야겠다고 생각했다.

3과 7의 차를 저장하고~ 0과 3의 차를 저장하고 그것을 리스트에 넣어서 min 써야겠다~

하지만..

-59 -36 -13 1 -53 -92 -2 -96 -54 75

완전탐색을 하려면 -59와 75까지 n번,,, -36과 75까지 n번..

n^2번이 걸리겠구나 뒤늦게 깨닳았다. 거기에다가 min 까지쓰면 n^2을 한번 더 실행....

주어진 n의 개수를 떠나서 5개만 넘어가도 알 수 있는 완전탐색을 하면... 안되겠는 문제다... 

어쨌든.. 여러생각끝에 정렬을 해야하는 문제겠거니 했다. 

저번에 포스팅 했듯이..

https://jellysbin.tistory.com/16?category=942615 

[파이썬]코딩테스트 문제 유형 - 정렬 : Tim sort

있는거 가져다 써야한다. 언어를 떠나서.. 가져다 쓰자..!

요약 1. 완전탐색하면 코드도 길어지고, 시간이 오래걸린다는것 인지    2. sort   3. 정렬한 arr에서 우측값을 빼서 그것을 리스트에저장해서 최소값 찾기

절대차가 저장된 배열안에서 절대차의 최소값 찾으면 끝난다. 참고로 min 함수는 선형탐색시간이 걸린다..

def minimumAbsoluteDifference(arr):
    arr.sort() #O(nlogn)
    dif = []
    for i in range(len(arr)-1): #O(n)
        d = abs(arr[i] - arr[i+1])
        dif.append(d)
    return min(dif) #O(n)

3. 우리 모두 화이팅!