1007. Minimum Domino Rotations For Equal Row

링크: https://leetcode.com/problems/minimum-domino-rotations-for-equal-row/

Minimum Domino Rotations For Equal Row - LeetCode

 2개의 도미노들 중 위아래 하나의 라인에서 같은 숫자가 이어지게끔 만드는 swap 개수 중 작은 값을 리턴하는 문제

 

class Solution {
public:
    int minDominoRotations(vector<int>& tops, vector<int>& bottoms) {
        int topCnt = 0;
        int bottomCnt = 0;
        int total = 0;
        
        for(int i = 0; i < tops.size(); i++){
            if(tops[0] != tops[i] && tops[0] != bottoms[i]){
                topCnt = -1;
            }
            
            if(bottoms[0] != tops[i] && bottoms[0] != bottoms[i]){
                bottomCnt = -1;
            }
            
            if(tops[i] == bottoms[i]){
                continue;
            }
            
            if(topCnt != -1 && tops[0] != tops[i]){
                topCnt++;
            }
            
            if(bottomCnt != -1 && bottoms[0] != bottoms[i]){
                bottomCnt++;
            }
            total++;
        }
        
        int ans = INT_MAX;
        
        if(topCnt != -1){
            ans = min(topCnt, total - topCnt);
        }
        
        if(bottomCnt != -1){
            ans = min(ans, min(bottomCnt, total - bottomCnt));
        }
        return ans == INT_MAX ? -1 : ans;
    }
};

 bottom과 top에서 첫 번째 값과 다른 값들을 각 라인에서 세고 중복을 제외한 totalCnt에서 다른 값 카운트를 빼서 그 중 작은 값을 반환한다.

 

time complexity: O(N)

space complexity: O(1) except for given memories