짬뽕얼큰하게의 맨땅에 헤딩 :: '2025/05/03 글 목록

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

Leetcode Problem:

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;
    }
};

'알고리즘' 카테고리의 다른 글

Domino and Tromino Tiling  (1) 2025.05.05
Number of Equivalent Domino Pairs  (0) 2025.05.04
Push Dominoes  (2) 2025.05.02
Maximum Number of Tasks You Can Assign  (1) 2025.05.01
Find Numbers with Even Number of Digits  (0) 2025.04.30
블로그 이미지

짬뽕얼큰하게

,