문제

You are given an integer array nums and an integer k.

An integer h is called valid if all values in the array that are strictly greater than h are identical.

For example, if nums = [10, 8, 10, 8], a valid integer is h = 9 because all nums[i] > 9 are equal to 10, but 5 is not a valid integer.

You are allowed to perform the following operation on nums:

Select an integer h that is valid for the current values in nums.
For each index i where nums[i] > h, set nums[i] to h.
Return the minimum number of operations required to make every element in nums equal to k. If it is impossible to make all elements equal to k, return -1.

문제 번역

정수 배열 nums와 정수 k가 주어집니다.

어떤 정수 h는 다음 조건을 만족할 때 유효한(valid) 값이라고 합니다:

배열에서 h보다 엄격히 큰 모든 값들이 동일해야 합니다.

예를 들어, nums = [10, 8, 10, 8]인 경우, h = 9는 유효한 정수입니다. 왜냐하면 9보다 큰 모든 nums[i]는 10으로 동일하기 때문입니다. 하지만 h = 5는 유효하지 않습니다.

다음과 같은 연산을 nums에 대해 수행할 수 있습니다:

현재 nums 배열에 대해 유효한 정수 h를 선택합니다.

그런 다음, 모든 인덱스 i에 대해 nums[i] > h인 경우, 해당 값을 h로 설정합니다. 즉, nums[i] = h로 만듭니다.

모든 배열의 원소를 k로 만들기 위해 필요한 최소 연산 횟수를 반환하세요. 만약 모든 원소를 k로 만드는 것이 불가능하다면 -1을 반환하세요.

---

Testcase

Example 1:

Input: nums = [5,2,5,4,5], k = 2

Output: 2

Explanation:

The operations can be performed in order using valid integers 4 and then 2.

Example 2:

Input: nums = [2,1,2], k = 2

Output: -1

Explanation:

It is impossible to make all the values equal to 2.

Example 3:

Input: nums = [9,7,5,3], k = 1

Output: 4

Explanation:

The operations can be performed using valid integers in the order 7, 5, 3, and 1.

Testcase 번역

예제 1:

입력: nums = [5,2,5,4,5], k = 2

출력: 2

설명: 유효한 정수 4와 그 다음으로 2를 순서대로 사용하여 연산을 수행할 수 있습니다.

예제 2:

입력: nums = [2,1,2], k = 2

출력: -1

설명: 모든 값을 2로 만드는 것은 불가능합니다.

예제 3:

입력: nums = [9,7,5,3], k = 1

출력: 4

설명: 유효한 정수들을 7, 5, 3, 1의 순서로 사용하여 연산을 수행할 수 있습니다.

---

from typing import List

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        for n in nums:
            if n < k: // 문자에서 모든 수를 k로 만들어야 하는데 k보다 작은 값이 커질 수 없기에 이 경우는 불가능.
                return -1 
        
        single_nums = set(nums) // 중복을 제거한 숫자들의 집합
        cnt = 0

        for x in single_nums:
            if x > k: // k보다 큰 서로 다른 수의 개수를 센다.
                cnt += 1
        
        return cnt

• 모든 숫자를 k로 만들어야 하기 때문에 K보다 작은 값이 리스트안에 존재한다면 불가능하다.
• k보다 큰 값을 줄여나갈 때, 같은 값들끼리만 한 번에 줄일 수 있습니다. 즉, k보다 큰 서로 다른 값의 개수만큼 연산이 필요하다.

예시 1

nums = [5,2,5,4,5], k = 2일 때

• set(nums) = {2,4,5}
• k보다 큰 값 = {4 , 5} => 2개
• 반환값 = 2

예시 2

nums = [2, 1, 2], k = 2

• 1 < 2 → 불가능 → -1 반환

예시 3

nums = [9,7,5,3], k = 1

• set(nums) = {3, 5, 7, 9}
• k보다 큰 값 = 4개
• 반환값: 4