2033. Minimum Operations to Make a Uni-Value Grid

https://leetcode.com/problems/minimum-operations-to-make-a-uni-value-grid/

난이도 : medium

문제

입력으로 들어오는 2차원 원소의 값을 모두 같은 값으로 만들어야한다. 같은 값으로 만들때 최소의 비용을 반환하라.

 

해당 문제는 x 의 값을 빼거나 더해서 배열의 모든 원소를 같은 값으로 만드는 문제이다. 필자는 2차원 데이터를 1차원으로 만들고 정렬을 통하여 중간값 mid을 찾고, 각각의 모든 요소를 중간값으로 만들때 차이값을 x 로 나누어서 풀이하였다. 

 

소스코드

class Solution {
public:
    int minOperations(vector<vector<int>>& grid, int x) {
        
        // grid 의 모든 원소 만큼 1차월 배열을 만든다.
        vector<int> arr(grid.size() * grid[0].size());
        
        int index = 0;
        for(int i=0; i<grid.size(); i++) {
            for(int j=0; j<grid[i].size(); j++, index++) {
                arr[index] = grid[i][j];
            }
        }
        
        // 정렬을 한다 O(n * log n)
        sort(arr.begin(), arr.end());
        
        // 중간 값을 찾는다.
        int mid = arr[arr.size()/2];
        
        int count = 0;
        for(int i = 0; i < arr.size(); i++)  {
            int cand = 0;
            
            if (arr[i] == mid) {
                cand = 0;
            }
            else if(arr[i] < mid) {
                int value = mid - arr[i];
                // 차이값을 계산한다.
                
                // 차이값에서 x 나눈후 나머지가 있다면 문제의 조건중 모두 같은 수를 만들 수 없다. - 1 리턴한다.
                if (value % x)
                    return -1;
                
                count += value / x;
            }
            else if(arr[i] > mid) {
                int value = arr[i] - mid;
                // 차이값을 계산한다.
                
                // 차이값에서 x 나눈후 나머지가 있다면 문제의 조건중 모두 같은 수를 만들 수 없다. - 1 리턴한다.
                if  (value % x) 
                    return - 1;
                
                count += value / x;
            }
        }
        
        return count;
    }
};