Minimum Operations to Exceed Threshold Value II

문제 설명

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

그리고, 다음과 같은 연산을 수행하니다.

1. nums에서 가장 작은 두 정수 x와 y를 선택합니다.
2. x와 y를 nums에서 제거합니다.
3. (min(x, y) * 2 + max(x, y))를 nums의 임의의 위치에 삽입합니다.

위 연산은 nums에 최소 두 개의 요소가 있을 때만 실행할 수 있습니다.

모든 배열 요소가 k 이상이 되도록 하는 최소 연산 횟수를 반환합니다.

문제 풀이

1. 주어진 배열 nums의 모든 요소를 힙에 추가합니다.
2. 힙의 길이가 2보다 작거나, 힙의 최솟값이 k를 초과할 때까지 다음 과정을 반복합니다:
   • 힙에서 가장 작은 두 요소를 꺼냅니다.
   • (min(x, y) * 2 + max(x, y))를 계산하여 힙에 추가합니다.
   • 연산 횟수를 증가시킵니다.
3. 현재까지의 연산 횟수를 반환합니다.

import { Heap } from '@algorithm/lib';
 
export function minOperations(nums: number[], k: number): number {
  const heap = new Heap<number>((a, b) => a - b);
  nums.forEach((num) => {
    heap.push(num);
  });
 
  let operation = 0;
  while (1 < heap.length && heap.peek !== undefined && heap.peek < k) {
    const x = heap.pop() ?? 0;
    const y = heap.pop() ?? 0;
    heap.push(2 * x + y);
    operation += 1;
  }
  return operation;
}

복잡도

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