1200. Minimum Absolute Difference

https://leetcode.com/problems/minimum-absolute-difference/

 

문제를 풀다가 내 자신이 바보같지만... 정리하는 시간을 가져보았다.

 

문제 설명 전문

Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements.

Return a list of pairs in ascending order(with respect to pairs), each pair [a, b] follows

a, b are from arra < bb - a equals to the minimum absolute difference of any two elements in arr

ex:
Input: arr = [3,8,-10,23,19,-4,-14,27]
Output: [[-14,-10],[19,23],[23,27]]

 

난 이것을 해결하기 위해 다음처럼 문제를 풀었다.

 

class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        Arrays.sort(arr);
        List<List<Integer>> result = new ArrayList<>();
        int minDiff = Integer.MAX_VALUE;
        for(int i = 0; i < arr.length-1; i++){
            int target1 = arr[i];
            for(int j = i+1; j < arr.length; j++){ <== 불필요한 반복문
                int target2 = arr[j];
                int subNum = Math.abs(target1 - target2);
                minDiff = Math.min(minDiff, subNum);
            }
        }
        
        for(int i = 0; i < arr.length-1; i++){
            List<Integer> tempList = new ArrayList<>();
            int target1 = arr[i];
            for(int j = i+1; j < arr.length; j++){  <== 불필요한 반복문
                int target2 = arr[j];
                int subNum = Math.abs(target1 - target2); <== 이미 정렬했는데 고려 안해도됌
                if(subNum == minDiff){
                    tempList.add(target1);
                    tempList.add(target2);
                }
                result.add(tempList);
                break;
            }
        }
        
    
        return result;
    }
}

 

사실 문제는 그렇게 어렵지 않고 방법을 뭔가 알겠는데 문제는 효율적이지 못하고, 뭔가 불필요한 작업을 하고있다는 사실이다.

 

그렇기 때문에 Time Limit Exceeded 가 뜨고야 말았다. (난 바보 ㅠ...)

 

모든 성분을 일일이 확인해가며 최소한의 숫자 차이가 얼마인지 판단하고, 그 다음에 이를 바탕으로 다시 한 번 반복문을 이용해서 해당되는 수를 List에 담으면 된다

 

이 흐름을 코드로 구현하면서 내가 저지른 실수는 다음과 같다. 

 

이미 정렬을 했는데 반복문을 더 쓸 필요가 없다. 순서대로 해당 조건에 맞는지만 판단하면 됨

 

그래서 짧은 시간이 걸릴 것을 한 번더 쓸데없이 돌리니 시간이 배가 걸리니 테스트를 통과하질 못한 것이다.

 

그래서 다음과 같이 수정했다. 

 

class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        Arrays.sort(arr);
        List<List<Integer>> result = new ArrayList<>();
        int minDiff = Integer.MAX_VALUE;
        for(int i = 0; i < arr.length-1; i++){
            minDiff = Math.min(minDiff, arr[i+1]-arr[i]);
        }
        
        for(int i = 0; i < arr.length-1; i++){
            List<Integer> tempList = new ArrayList<>();
            int subNum = arr[i+1] - arr[i];
            if(subNum == minDiff){
                tempList.add(arr[i]);
                tempList.add(arr[i+1]);
                result.add(tempList);
            }
        }
    
        return result;
    }
}

 

생각보다 간단한데 너무 장황하게 뭘 하려고 한 것 같아 아쉬움에 글을 적어본다... 또르르...