문제

Minimum Number of Operations to Make Elements in Array Distinct

---

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.

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.

번역

정수 배열 nums가 주어진다. 이 배열의 모든 요소가 서로 다른 값이 되도록 만들어야 한다. 이를 위해 다음과 같은 작업을 원하는 만큼 수행할 수 있다.

배열의 앞에서 3개의 요소를 제거한다. 만약 배열의 길이가 3보다 작다면, 남아 있는 모든 요소를 제거한다.

빈 배열은 모든 요소가 서로 다른 것으로 간주 된다. 배열의 모든요소가 서로 다르도록 만들기 위해 필요한 최소 작업 횟수를 반환하라.

---

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.

예제 1:

입력: nums = [1,2,3,4,2,3,3,5,7]
출력: 2

설명:

첫 번째 연산에서 앞의 3개의 요소가 제거되어 배열이 [4, 2, 3, 3, 5, 7]이 됩니다.

두 번째 연산에서 다음 3개의 요소가 제거되어 배열이 [3, 5, 7]이 됩니다. 이 배열은 모든 요소가 서로 다릅니다.

따라서 정답은 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.

예제 2:

입력: nums = [4,5,6,4,4]
출력: 2

설명:

첫 번째 연산에서 앞의 3개의 요소가 제거되어 배열이 [4, 4]이 됩니다.

두 번째 연산에서 남은 모든 요소가 제거되어 배열이 비게 됩니다.

따라서 정답은 2입니다.

Example 3:

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

Output: 0

Explanation:

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

예제 3:

입력: nums = [6,7,8,9]
출력: 0

설명:

이 배열은 이미 모든 요소가 서로 다릅니다.

따라서 아무런 연산 없이도 조건을 만족하므로 정답은 0입니다.

Constraints:

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

---

from collections import deque
from typing import List


class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        count = 0
        numQueue = deque(nums)
        while len(numQueue) > 0:
            if len(set(numQueue)) == len(numQueue):
                return count
            for _ in range(min(3,len(numQueue))):
                numQueue.popleft()
            count += 1
        return count

여기서 중요한 로직은

      if len(set(numQueue)) == len(numQueue):
          return count
      for _ in range(min(3,len(numQueue))):
          numQueue.popleft()

이 부분이다.

어떻게 길이로 중복을 확인하는지 궁금할텐데 과정은 이렇다.
첫번째 testcase인 nums = [1,2,3,4,2,3,3,5,7]이것으로 예시를 들어보겠다.

1회차

• set(numQueue) = {1, 2, 3, 4, 5, 7} (중복 제거)
• len(numQueue) = 9
• len(set(numQueue)) = 6
  ➡️서로 다르다 -> 중복 존재

-> 첫 3개 제거

• numQueue → [4, 2, 3, 3, 5, 7]
• count = 1

2회차

• set(numQueue) = {2, 3, 4, 5, 7} (중복 제거)
• len(numQueue) = 6
• len(set(numQueue)) = 5
  ➡️서로 다르다 -> 중복 존재

-> 첫 3개 제거

• numQueue → [3, 5, 7]
• count = 2

2회차

• set(numQueue) = {3, 5, 7} (중복 제거)

• len(numQueue) = 3

• len(set(numQueue)) = 3
  ➡️서로 같다 -> 중복 없음

• 반복 종료, return count = 2

이런식으로 길이를 비교해서도 중복 유무를 비교할 수 있다.