Minimum Operations to Make a Uni-Value Grid

문제 설명

• m x n 크기의 2차원 정수 배열 grid가 주어집니다.
• 정수 x 가 주어집니다.
  • x는 한 번의 연산에서 grid의 임의의 원소에서 더하거나 뺄 수 있는 값을 의미합니다.
• 모든 원소가 동일한 값을 가지는 uni-value grid를 만들기 위한 최소 연산 횟수를 반환하여야 합니다..
  • 만약 모든 원소를 같은 값으로 만드는 것이 불가능하다면 -1을 반환합니다.

문제 풀이

Median Finding

1. 배열 정렬
   • 2차원 배열을 1차원 배열로 변환한 후, 오름차순으로 정렬
   • 정렬된 배열에서 중앙값(median)을 찾아 목표 값으로 설정
2. 최소 연산 횟수 계산
   • 모든 원소를 중앙값(median)으로 만들기 위한 연산 횟수를 계산합니다.
   • 변환 가능 여부 확인
     • (목표 값 - 원소 값) % x === 0 이 아니라면, 변환할 수 없으므로, -1을 반환
   • (목표 값 - 원소 값) / x 만큼의 연산 횟수가 필요하므로, 해당 값을 통해 최소 연산 횟수를 계산

• 왜 중앙값(median)을 목표 값으로 설정해야 할까?
  • 중앙값을 기준으로 변환할 때, 전체 연산 횟수가 최소가 됩니다.
  • 중앙값보다 작은 수들은 증가해야하고, 큰 수들은 감소해야 하는데, 중앙값이 최소 횟수로 변환할 수 있는 최적의 지점이기 때문입니다.

export function minOperations(grid: number[][], x: number): number {
  const values = grid.flat().sort((a, b) => a - b);
  const midValue = values[Math.floor(values.length / 2)];
 
  let operations = 0;
  for (const value of values) {
    const diff = Math.abs(midValue - value);
    if (diff % x !== 0) {
      return -1;
    }
    operations += diff / x;
  }
  return operations;
}

복잡도

• 시간 복잡도: $O(m \cdot n \cdot \log_2(m \cdot n))$
• 공간 복잡도: $O(m \cdot n)$