LeetCode [1200]: Minimum Absolute Difference

📌 LeetCode [1200]: Minimum Absolute Difference

🔗 문제 링크

---

문제 설명 📄

정수 배열 arr가 주어졌습니다. 배열에서 두 수의 차이의 절대값이 최소가 되는 모든 쌍을 찾고, 이를 정렬된 형태로 반환하세요.

• 반환된 쌍은 오름차순으로 정렬되어야 합니다.
• 각 쌍은 [a, b] 형태이며, (a < b).

---

문제 접근 방식 📋

1. 집합 활용:
   • 배열을 정렬한 뒤, 집합을 사용하여 숫자의 존재를 빠르게 확인.
2. 최소 차이 탐색:
   • 인접한 두 원소 간의 차이를 계산하여 최소값을 갱신.
3. 결과 쌍 수집:
   • 집합에서 최소 차이를 만족하는 쌍을 찾아 결과에 추가.

---

Solution 💻

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        answer = set()
        pattern = {i for i in arr}

        arr.sort()
        minValue = float('inf')
        for i in range(len(arr)-1):
            if abs(arr[i] - arr[i+1]) < minValue:
                minValue = abs(arr[i] - arr[i+1])

        for i in pattern:
            if i + minValue in pattern:
                answer.add((i, i + minValue))
            elif i - minValue in pattern:
                answer.add((i - minValue, i))

        return sorted(answer)

시간 복잡도 ⏲️

• 정렬: (O(n log n)), (n)은 배열의 크기.
• 집합 탐색: (O(n)).
• 최종 시간 복잡도: (O(n^2)) (최악의 경우).

공간 복잡도 🗄️

• 집합 및 결과 사용 공간: (O(n)).
• 총 공간 복잡도: (O(n)).

---

리팩토링 🛠️

개선된 코드

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        arr.sort()
        min_diff = float('inf')
        result = []

        for i in range(len(arr) - 1):
            diff = arr[i + 1] - arr[i]
            if diff < min_diff:
                min_diff = diff
                result = [[arr[i], arr[i + 1]]]
            elif diff == min_diff:
                result.append([arr[i], arr[i + 1]])

        return result

리팩토링 후 시간 복잡도 ⏲️

• 정렬: (O(n log n)), (n)은 배열의 크기.
• 인접한 원소 비교: (O(n)).
• 최종 시간 복잡도: (O(n log n)).

리팩토링 후 공간 복잡도 🗄️

• 결과 리스트: (O(n)).
• 총 공간 복잡도: (O(n)).

---