'2025/05/03'에 해당되는 글 1건

Leetcode Problem:

• Minimum Domino Rotations For Equal Row

Summary

• The problem is to find the minimum number of rotations required to make all values in the tops or bottoms array equal
• The function takes two arrays, tops and bottoms, as input and returns the minimum number of rotations
• If it's not possible to make all values equal, the function returns -1.

Approach

• The solution code uses a two-pass approach
• First, it checks if it's possible to make all values in the tops or bottoms array equal by checking if there's a common value between the two arrays
• If it's not possible, the function returns -1
• Otherwise, it counts the number of rotations required to make all values in the tops or bottoms array equal.

Complexity

• O(n), where n is the length of the tops and bottoms arrays
• The function makes two passes through the arrays, one for each possible common value.

Explanation

• The solution code first checks if it's possible to make all values in the tops or bottoms array equal by checking if there's a common value between the two arrays
• If it's not possible, the function returns -1
• Otherwise, it counts the number of rotations required to make all values in the tops or bottoms array equal
• The function uses two counters, cnt1 and cnt2, to count the number of rotations required to make all values in the tops and bottoms arrays equal, respectively
• The function returns the minimum of cnt1 and cnt2.

Solution Code:

class Solution {
public:
    int minDominoRotations(vector& tops, vector& bottoms) {
        int cur = tops[0];
        bool success = true;
        for(int i = 0 ; i < tops.size(); i++){
            if(tops[i] == cur || bottoms[i] == cur) continue;
            success = false;
            break;
        }
        if(!success){
            success = true;
            cur = bottoms[0];
            for(int i = 0 ; i < tops.size(); i++){
                if(tops[i] == cur || bottoms[i] == cur) continue;
                success = false;
                break;
            }
        }
        if(!success) return -1;

        int cnt1 = 0;
        int cnt2 = 0;
        for(int i = 0 ; i < tops.size(); i++){
            if(tops[i] != cur) cnt1++;
            if(bottoms[i] != cur) cnt2++;
        }
        return cnt1 < cnt2 ? cnt1 : cnt2;
    }
};