[LeetCode] 1007. Minimum Domino Rotations For Equal Row

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

Minimum Domino Rotations For Equal Row - LeetCode

Minimum Domino Rotations For Equal Row

 

 

앞,뒤에 주사위 숫자가 적혀있는 도미노 타일이 있다. 이 타일을 쭉 나열한 모습이 주어졌을때,

도미노를 뒤집어 한 면의 도미노 타일이 모두 같아지게 하는데,

이 때 도미노를 뒤집는 최소 횟수를 구하여라.

 

모든 도미노 타일이 같아지려면 모든 타일이 맨 앞 도미노의 앞/뒤(Top / Bottom 이지만 편의상.) 타일에 포함되어야 한다. 그렇지 않을 경우엔 바로 -1을 출력해준다.

 

i번째 도미노의 앞 타일이 제일 앞 도미노의 앞 타일과 같은 개수 => tb[0][0]

i번째 도미노의 앞 타일이 제일 앞 도미노의 뒷 타일과 같은 개수 => tb[1][0]

i번째 도미노의 뒷 타일이 제일 앞 도미노의 앞 타일과 같은 개수 => tb[0][1]

i번째 도미노의 뒷 타일이 제일 앞 도미노의 뒷 타일과 같은 개수 => tb[1][1]

 

를 따로 체크해주고, i번째 도미노의 앞,뒤 타일이 같은 경우도 세어준다. => tb[0][2]

 

이렇게 되면, 답이 존재할 경우엔 tb[0][0] + tb[0][1] - tb[0][2] 또는 tb[1][0] + tb[1][1] - tb[0][2] 가 전체 도미노 개수와 같게 된다. (아닐 경우 -1 return)

마지막으로, 제일 앞 도미노의 앞 타일이 모두 존재할 경우 (즉, tb[0][0] + tb[0][1] - tb[0][2] 가 도미노 개수와 같을 경우)

 

앞 타일에 그 타일이 있는 경우는 tb[0][0]

뒷 타일에 그 타일이 있는 경우는 tb[0][1] 이므로

 

뒤집어야할 개수는 min(전체 도미노타일 개수 - 앞 타일 개수, 전체 도미노타일 개수 - 뒷 타일 개수) 가 된다.

 

뒷 타일의 경우도 이렇게 해서

 

전체적으로 가장 작은 값을 출력해주자.

 

전체 풀이 코드

 

class Solution {
public:
    int minDominoRotations(vector<int>& tops, vector<int>& bottoms) {
        int tb[2][3] = {0}, n = tops.size(), t[2] = {tops[0], bottoms[0]}, ret = INT_MAX;
        for (int i=0; i<n; i++) {
            int d[2] = {tops[i], bottoms[i]};
            for (int j=0; j<2; j++) for (int k=0; k<2; k++) if (t[j]==d[k]) tb[j][k]++;
            if (d[0]==d[1]) tb[0][2]++;
        }
        for (int i=0; i<2; i++) if (tb[i][0]+tb[i][1]-tb[0][2] == n) ret = min(ret, min(n-tb[i][0], n-tb[i][1]));
        return ret==INT_MAX?-1:ret;
    }
};