[Java]해커랭크 - Minimum Absolute Difference in an Array

 

정수형 배열이 주어지면, 중복되지 않는 쌍(pair)을 만들어

각 쌍에서 원소들 간의 차이 값에 대한 절대값이 가장 최소인 값이 얼마인지 반환하는 문제이다. 

 

 

간단한 문제라 아래와 같이 풀이 후 Submit을 눌렀는데...

static int minimumAbsoluteDifference(int[] arr) {
    int min = Integer.MAX_VALUE;

    for(int i=0; i<arr.length-1; i++){
        for(int j=i+1; j<arr.length; j++){
            min = Math.min(min, Math.abs(arr[i]-arr[j]));
        }
    }
    return min;
}

 

두 개의 Test Case에서 Fail이 났고, Fail 사유는 시간초과. 

 

이중 for문으로 시간복잡도가 O(n^2)이다.

 

그래서 한번의 for문을 이용해 풀어야한다.. 

정렬 후에 인접한 값을 빼주는 방법을 이용하면 한번의 for문으로 가능.

static int minimumAbsoluteDifference(int[] arr) {
    int min = Integer.MAX_VALUE;

    Arrays.sort(arr);

    for(int i=0; i<arr.length-1; i++){
        min = Math.min(min, Math.min(min, Math.abs(arr[i]-arr[i+1])));
    }
    return min;
}