LeetCode - 1007. Minimum Domino Rotations For Equal Row

문제링크

 

문제 설명

도미노 타일들이 일렬로 나열되어 있으며,
각 도미노의 윗면과 아랫면 숫자가 tops[i]와 bottoms[i]로 주어집니다. (각 숫자는 1부터 6 사이입니다.)

각 도미노는 회전시킬 수 있습니다, 즉, tops[i]와 bottoms[i]의 값을 서로 바꿀 수 있습니다.

당신의 목표는 다음 중 하나를 만드는 것입니다:

• tops 배열의 모든 값이 동일해지도록,
• 또는 bottoms 배열의 모든 값이 동일해지도록.

가능하다면, 그렇게 만들기 위해 필요한 최소 회전 횟수를 반환하고, 불가능하다면 -1을 반환하세요.

제한 사항

• 2 <= tops.length <= 2 * 10^4
• bottoms.length == tops.length
• 1 <= tops[i], bottoms[i] <= 6

예시

Example 1:

Input: tops = [2,1,2,4,2,2], bottoms = [5,2,6,2,3,2]
Output: 2
Explanation: 
The first figure represents the dominoes as given by tops and bottoms: before we do any rotations.
If we rotate the second and fourth dominoes, we can make every value in the top row equal to 2, as indicated by the second figure.

 

Example 2:

Input: tops = [3,5,1,2,3], bottoms = [3,6,3,3,4]
Output: -1
Explanation: 
In this case, it is not possible to rotate the dominoes to make one row of values equal.

풀이 흐름

• 도미노의 개수가 최대 20,000이고 숫자는 1~6까지 이므로 브루트 포스를 사용해도 괜찮다고 판단했습니다.
• tops와 bottoms를 순회하면서 1로 통일한다고 가정할 때 top으로 통일하려면 몇번 회전해야 하는지, bottom으로 통일하려면 몇번 회전해야 하는지 구해준 후 그중 최솟값을 min변수에 저장했습니다.
• 만약 top과 bottom 둘 다 해당 숫자가 없으면 break로 더 이상 탐색하지 않았습니다.
• 마지막에 min의 값이 초기 세팅 값인 20,001과 같으면 -1을 다르면 min값을 반환시켰습니다.

코드

class Solution {
    public int minDominoRotations(int[] tops, int[] bottoms) {
        int min = 20001;
        for (int i = 1; i <= 6; i++) {
            int topc = 0;
            int bottomc = 0;
            boolean end = true;
            for (int j = 0; j < tops.length; j++) {
                if (tops[j] == i && bottoms[j] == i) {
                    continue;
                }
                if (tops[j] == i) {
                    bottomc++;
                } else if (bottoms[j] == i) {
                    topc++;
                } else {
                    end = false;
                    break;
                }
            }
            if (end) {
                min = Math.min(topc, Math.min(bottomc, min));
            }
        }
        return min == 20001 ? -1 : min;
    }
}