[Greedy] hackerrank - Minimum Absolute Difference in an Array

https://www.hackerrank.com/challenges/minimum-absolute-difference-in-an-array/problem?isFullScreen=true

Minimum Absolute Difference in an Array | HackerRank

 

문제

주어진 코드는 minimumAbsoluteDifference 함수에서 정수 배열(리스트) arr의 최소 절대 차이를 구하는 문제이다.

 

예를들어 input이

3
3 -7 0

 

이라면, output은

3

 

 

input

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

 

output

1

 

 

내 풀이

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

class Result {

    /*
     * Complete the 'minimumAbsoluteDifference' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts INTEGER_ARRAY arr as parameter.
     */

    public static int minimumAbsoluteDifference(List<Integer> arr) {
        int result = Integer.MAX_VALUE;
        
        Collections.sort(arr);
        
        for (int i =0; i < arr.size()-1; i++){
            result = Math.min(result, Math.abs(arr.get(i) - arr.get(i+1)));
        }
                
        return result;
    }

}

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

        int n = Integer.parseInt(bufferedReader.readLine().trim());

        String[] arrTemp = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

        List<Integer> arr = new ArrayList<>();

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

        int result = Result.minimumAbsoluteDifference(arr);

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

        bufferedReader.close();
        bufferedWriter.close();
    }
}

 

절댓값의 총 합은 더하는 순서가 중요하지 않다.

→ 현재의 선택이 미래 선택에 영향을 미치지 않으므로

이 문제는 그리디 알고리즘으로 풀 수 있는 문제이다.

 

이 문제를 해결하기 위해서는 배열을 정렬한 후 인접한 두 값의 차이 중 최소값을 찾아야 한다.

왜냐하면 배열이 정렬되면 인접한 값들 간의 차이가 최소화되기 때문이다.

 

Test case로 뭐가 나올 지 모르니

int result = Integer.MAX_VALUE; 로 설정해주자.

 

---

요약

1. 배열을 정렬합니다.
2. 정렬된 배열에서 인접한 값들의 절대 차이를 계산하고, 그 중 최소값을 찾습니다.