Minimum Operations to Make Array Values Equal to K

문제 설명

• 정수 배열 nums와 정수 k가 주어집니다.
• num에 다음과 같은 연산을 수행할 수 있습니다.
  • 유효한 정수 h를 선택합니다.
    • h는 현재 배열에서 h보다 큰 값들이 모두 동일할 때 유효합니다.
      • 예: [10, 8, 10, 8]일 때, h=9는 유효합니다. (9보다 큰 값은 모두 10)
        • 하지만 h = 5는 유효하지 않습니다. (5보다 큰 값이 8과 10으로 서로 다름)
  • 모든 nums[i] > h의 값을 h로 변경합니다.
• 위 연산을 사용해 모든 요소를 k로 만드는 최소 연산 횟수를 반환해야 합니다.
  • 만약, 불가능하면 -1을 반환합니다.

문제 풀이

Set

💡 아이디어

• k보다 작은 값이 있다면 불가능 → -1
• k보다 큰 서로 다른 값의 개수 = 필요한 최소 연산 횟수

1. k보다 작은 값이 있는 경우 → 불가능
   • 모든 요소를 k로 만들기 위해서는 모든 값이 k 이상이어야 합니다.
   • 하지만, nums에 k보다 작은 값이 하나라도 있다면, 해당 값은 아무리 연산을 해도 k이상이 될 수 없습니다.
   • 따라서, 이 경우 즉시 -1을 반환합니다.
2. k보다 큰 값을 k로 낮추는 과정
   • 문제에서 주어진 연산은 h보다 큰 값들을 모두 h로 낮추는 연산입니다.
   • 이때 유효한 h는 nums내에서 h보다 큰 값들이 모두 동일한 경우에만 선택할 수 있습니다.
   • 이 조건을 사용하여 매 연산 마다 서로 다른 큰 수 중 하나만 제거할 수 있습니다.
     • 예: nums = [12, 12, 10, 10, 8, 8, 5], k = 5인 경우,
     • 가능한 유효 h는 11 → 9 → 7 → 5, 이런 식으로 하나씩 낮추면서 처리됩니다.
   • 따라서, k보다 큰 서로 다른 값의 개수만큼의 연산이 필요합니다.
   • Set을 사용해 k보다 큰 서로 다른 값들을 저장하고, 그 크기(set.size)를 반환하면 필요한 연산의 최소 횟수가 됩니다.

export function minOperations(nums: number[], k: number): number {
  const set = new Set<number>();
 
  for (const num of nums) {
    if (num < k) {
      return -1;
    }
    if (k < num) {
      set.add(num);
    }
  }
  return set.size;
}

복잡도

• 시간 복잡도: $O(n)$
• 공간 복잡도: $O(n)$