Java/Algorithm

[Java-Algorithm] HackerRank Java - Minimum Absolute Difference in an Array 풀이

Jeong Jeon
반응형

1). 문제 : www.hackerrank.com/challenges/minimum-absolute-difference-in-an-array

 

Minimum Absolute Difference in an Array | HackerRank

Given a list of integers, calculate their differences and find the difference with the smallest absolute value.

www.hackerrank.com

2). 풀이 :

2중 For문으로 처음에 풀었다가, Timeout으로 TestCase 몇개가 걸렸다.

아래 풀이의 KeyPoint는 인접한 값의 차이 = 최소값 이라는 점이다.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    // Complete the minimumAbsoluteDifference function below.
    static int minimumAbsoluteDifference(int[] arr) {
        int intMin = Integer.MAX_VALUE;
        //한번 Sorting해서 작은 값부터 시작한다.
        Arrays.sort(arr);
        for(int i=0; i<arr.length-1; i++){
            //앞뒤값 뺀것에 가장 작은 값 추출 => 인접한 값의 차이가 가장 작을 테니까.
            intMin = Math.min(intMin,Math.min(intMin,Math.abs(arr[i]-arr[i+1])));
        }
        return intMin;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int n = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        int[] arr = new int[n];

        String[] arrItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int i = 0; i < n; i++) {
            int arrItem = Integer.parseInt(arrItems[i]);
            arr[i] = arrItem;
        }

        int result = minimumAbsoluteDifference(arr);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}
반응형