[LeetCode] 3396. Minimum Number of Operations to Make Elements in Array Distinct (Python)

 

 

난이도: Easy

Problem Description

---

You are given an integer array nums. You need to ensure that the elements in the array are distinct. To achieve this, you can perform the following operation any number of times:

• Remove 3 elements from the beginning of the array. If the array has fewer than 3 elements, remove all remaining elements.

Note that an empty array is considered to have distinct elements. Return the minimum number of operations needed to make the elements in the array distinct.

 

Problem Example

---

Example 1:

Input: nums = [1,2,3,4,2,3,3,5,7]

Output: 2

Explanation:

• In the first operation, the first 3 elements are removed, resulting in the array [4, 2, 3, 3, 5, 7].
• In the second operation, the next 3 elements are removed, resulting in the array [3, 5, 7], which has distinct elements.

Therefore, the answer is 2.

Example 2:

Input: nums = [4,5,6,4,4]

Output: 2

Explanation:

• In the first operation, the first 3 elements are removed, resulting in the array [4, 4].
• In the second operation, all remaining elements are removed, resulting in an empty array.

Therefore, the answer is 2.

Example 3:

Input: nums = [6,7,8,9]

Output: 0

Explanation:

The array already contains distinct elements. Therefore, the answer is 0.

 

Constraints

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

 

 

✏️ Solution

---

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(0, n, 3):
            if n - i == len(set(nums[i:])):
                return i // 3
        
        return (i+3)//3

처음에는 위와 같이 문제를 해결했다.

 

0 부터 len(nums)까지 i를 3씩 더해가며 nums의 리스트를 확인했다.

예를 들면 다음과 같다.

nums = [1,2,3,4,2,3,3,5,7]

i = 0  ==> nums[i:] = [1,2,3,4,2,3,3,5,7]

i = 3 ==> nums[i:] = [4,2,3,3,5,7]

i = 6 ==> nums[i:] = [3,5,7]

 

이렇게 했을 때, 현재 nums[i:]의 길이와 set(nums[i:])의 길이가 같다고 한다면 모두 distinct하다고 판단할 수 있다.

따라서, 이 때는 i // 3을 return 하였다.

 

아무 조건도 만족 못하고 반복문을 빠져나왔다면, (i+3)//3을 return 하였다.

 

---

 

위 코드는 성능이 그렇게 좋지 않아서 다음과 같이 다시 구현했다.

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        n = len(nums)
        nums_set = set()

        for i in range(n-1, -1, -1):
            if nums[i] in nums_set:
                return i // 3 + 1            
            nums_set.add(nums[i])
        
        return 0

nums의 요소를 역순으로 하나씩 set()에 넣으면서, 만약 현재 nums[i]가 nums_set에 있으면 중복되는 것이기 때문에, i // 3+1을 return 하였다.

 

반복문을 빠져나오게 된다면 nums가 이미 모두 distinct하기 때문에 0을 반환해주었다.

 

 

⚙️ Runtime & Memory

---

위 코드

 

아래 코드

 

 

---

문제: 3396. Minimum Number of Operations to Make Elements in Array Distinct

 

깃허브: github

algorithmPractice/LeetCode/3656-minimum-number-of-operations-to-make-elements-in-array-distinct at main · laewonJeong/algorithm