[Array, Greedy, Sorting] Minimum Difference Between Largest and Smallest Value in Three Moves

https://leetcode.com/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves/description/?envType=daily-question&envId=2024-07-03

 

 

🔖 태그 🔖

Array, Greedy, Sorting

 

🔮 문제 🔮

정수 array가 있다.

3개를 뺐을 때, max(array) - min(array)의 최댓값을 구하라.

 

 

 

 

 

 

<깨알 정리>

list와 array의 차이는?

 

list는 여러 타입을, array는 단일 타입을 저장.

대신, array는 메모리도 효율적이고 속도도 빠르다.

 

 

 

 

 

 

---

 

 

 

 

 

 

✨ 인사이트 ✨

 

max(array) - min(array)를 줄이기 위해서는 array의 최솟값이나 최댓값만을 없애야 한다.

가장 작은 3개를 지우든가, 가장 적은 2개 & 가장 큰 1개를 지우든가, 가장 적은 1개 & 가장 큰 2개를 지우든가, 가장 큰 3개를 지우고 각 경우에서 max(array) - min(array)를 비교해 보자.

 

 

 

 

✨ 방법 1 ✨ - Sort + Greedy Deletion

다 좋은데 sorting 하는 데 time complexity가 O(nlogn)이 걸리기 때문에 바람직하지 않다.

게다가 space complexity 역시 O(n)이 걸려서(C++는 sorting 할 때 space complexity가 O(logn)이긴 함) 이것도 불만족스럽다.

 

 

 

 

✨방법 2

time complexity가 O(n), space complexity가 O(1)로 이전보다 훨씬 낫다.

 

앞서 말했듯, 최솟값과 최댓값만 고려하는 전략을 택한다. 전체를 sorting 할 필요가 없다!

3개를 지울 수 있기 때문에 가장 작은 4개와 가장 큰 4개를 고려하면 된다. (왜 3개가 아니라 4개냐면, 3개를 전부 최솟값에서 지우면 원래 4번째로 최솟값이던 친구가 새로운 최솟값이 되기 때문)

 

partial sort를 위해 아래 방법을 사용할 수 있다.

 

 

Java와 Python의 경우 heap을 사용할 수 있다.

 

heap에 대해 잠깐 알아보자.

 

Priority Queue: 각 요소가 우선순위를 가져, 높은 우선순위를 가진 요소가 먼저 처리. FIFO의 일반적인 Queue와는 다름.

 

heap은 min-heap과 max-heap으로 나뉜다. 둘이 큰 차이는 없다. min-heap에서는 가장 작은 값이 root에 있고, max-heap은 그 반대다.

 

 

max-heap은 자체 지원이 안 되지만 마이너스를 붙여서 우회적으로 사용할 수 있다.

 

https://www.geeksforgeeks.org/heap-data-structure/

 

알고리즘 순서는 다음과 같다.

 

먼저 기본 initialization 조지고, partial sort을 해서 최솟값 4개와 최댓값 4개를 찾는다.

 

 

최솟값 4개와 최댓값 4개를 순서대로 짝지은 4개의 쌍의 차이를 구하면 그중에서 가장 작은 친구가 우리가 구하려는 답이다!

 

 

 

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        nums_size = len(nums)
        if nums_size <= 4:
            return 0

        # Find the four smallest elements
        smallest_four = sorted(heapq.nsmallest(4, nums))

        # Find the four largest elements
        largest_four = sorted(heapq.nlargest(4, nums))

        min_diff = float("inf")
        # Four scenarios to compute the minimum difference
        for i in range(4):
            min_diff = min(min_diff, largest_four[i] - smallest_four[i])

        return min_diff

 

👉 Time Complexity가 O(n)인 이유

4개의 가장 작은(or 큰) 요소를 heap으로 고를 때,

n개의 요소들을 모두 훑어야 하고 O(n)

node가 4개인 heap에 요소를 집어넣을 때는 O(log4)만 필요하기 때문에

둘을 곱한 값인 O(n)이 필요하다.

 

👉 Space Complexity가 O(1)인 이유

node가 4개인 heap에는 꼴랑 O(4)만 필요하다.

따라서 O(1)