1200. Minimum Absolute Difference

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

팀 알고리즘 레포지토리 주소

문제 출처

[처음 생각한 접근 방법]

일단 두 수의 차이가 가장 작으려면, 가장 인접한 숫자여야 한다고 생각했습니다.

즉, 정렬 되어 있는 상태에서 양옆에 있어야 가장 인접한 숫자고 그럴 경우 두 수의 차이가 가장 작을 것이다.

따라서 아래와 같은 식으로 코드를 짜자고 마음을 먹었습니다.

1. 오름차순 정렬

2. 배열의 모든 원소들을 각각 인접한 요소끼리의 차를 구하고 그 값이 최솟값인 애를 pivot(기준)으로 둔다.

3. 배열의 모든 원소들의 각각 인접한 요소끼리의 차를 구하고 그 값이 pivot인 애를 리스트에 넣는다.

정렬

인접한 요소끼리의 차를 구한다. 여기선 모두 1이므로 pivot(기준)이 1이 됨.

마지막으로 차가 1(pivot)인 애들을 모두 구하면 되는데 위에선 {{1,2},{2,3},{3,4}}가 됩니다.

[Java 코드]

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        List<List<Integer>> answer = new LinkedList();
        Arrays.sort(arr);
        int pivot = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i+1] - arr[i] < pivot) pivot = arr[i] - arr[i+1];
        }

        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i+1] - arr[i] == pivot) {
                List temp = new LinkedList();
                temp.add(arr[i]);
                temp.add(arr[i+1]);
                answer.add(temp);
            }
        }

        return answer;
    }
}

[Kotlin 코드]

import java.util.*

class Solution {
    fun minimumAbsDifference(arr: IntArray): List<List<Int>> {
        val answer = LinkedList<List<Int>>()
        arr.sort()

        var pivot = Integer.MAX_VALUE
        for (i in 0..arr.size-2) {
            if (arr[i+1] - arr[i] < pivot) pivot = arr[i+1] - arr[i]
        }

        for (i in 0..arr.size-2) {
            if (arr[i+1] - arr[i] == pivot) {
                val list = LinkedList<Int>()
                list.add(arr[i])
                list.add(arr[i+1])
                answer.add(list)
            }
        }

        return answer
    }
}

시간복잡도는 Arrays.sort가 nlogn이고 나머지 for문은 전부 n이므로 O(nlogn)

공간복잡도는 최악의 경우 모든 요소가 들어갈 수 있으므로 O(n)이 되지 않을까 싶다.

 

[리트코드 답안]

Java, sorting, beats 100%, explained - LeetCode Discuss

두 번의 for문을 사용하지 않고 한 번의 for문으로 처리한 코드다.

clear의 시간복잡도가 n이므로 결과적으로 O(n^2)이 되지 않을까 싶다.