[Leetcode]1007. Minimum Domino Rotations For Equal Row

문제 요약

• 알고리즘 분류: Greedy
• 난이도: Medium
• 문제내용:
  • tops, bottoms 같은 길이 주사위 배열을 준다.
  • tops[i], bottoms[i]  같은 index위치끼리 바꿀수 있다.
  • top과 bottom을 바꾸면서 top이나 bottom중에서 같은 주사위 숫자가 같게 만들수 있을때 최소 몇번 바꾸면되는지 반환 하여라 만약 안될 경우 -1로 반환 하여라
• 사이트 주소: https://leetcode.com/problems/minimum-domino-rotations-for-equal-row/description/

문제풀이

모든 경우의 수로 답은 나오지 브루드포스로 풀경우에는 시간 초과가 나올것이다. 그래서 이번문제는 그리디로 풀어야 한다. 그리디 관련 설명은 아래글을 확인 해보면된다.

https://jih3508.tistory.com/70

[알고리즘 이론] 그리디(Greedy)

그리디는 구현보다 아이디어를 요구하는 문제이다. 모든것을 바꾸면서 경우의 수를 구할필요가 없다 그 이유는 모든 라인 같은 숫자를 만들어야 되기 때문에 top, bottom 0번째 값 기준으로 탐색을 시작해서 바꿔도 안되는것 있으면 바로 -1로 반환 하면 된다. 그렇지 않을경우 top이나 bottom 기준으로 바꾸면서  일정한 숫자로 유지하면되다. 그럼 나머지는 top bottom 기준 잡는것과 top[0], bottom[0]값을 기준점 잡기만 하면된다. 그럼 아래와 같은 4가지 경우가 나온다.

1. top[0]번째 숫자와 top일정하게 숫자로 기준으로 잡는것
2. top[0]번째 숫자와 bottom일정하게 숫자로 기준으로 잡는것
3. bottom[0]번째 숫자와   top일정하게 숫자로 기준으로 잡는것
4. bottom[0]번째 숫자와 bottom일정하게 숫자로 기준으로 잡는것

그리고 구현은 탐색해서 교환하는 구현은 아래와 같이 하면된다.

• top[0] 또는 bottom[0]값이 i번째 값이 다를경우
  • 바꾸는 값이 다르면 -1로 반환한다.
  • 같을경우 count를 +1 해준다.

4가지중 가장 적을값을 반환하거나 혹은 4가지 경우에서 안되는 경우 -1로 반환만 하면 된다. 이렇게 구현하면 시간복잡도는 O(N)만큼 나온다.

Code

Python

class Solution:
    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
        INF = 1e9
        def changeCount(value, tops, bottoms):
            count = 0

            for i in range(len(tops)):
                # 바꿀깞이 0번째 인덱스 값 같을 경우 바꾼다.
                if tops[i] != value:
                    if bottoms[i] == value:
                        count += 1
                    else:
                        # 아니면 그냥 바꾼다.
                        return INF

            return count

        result = INF
        #  top이나 bootop [0]번째 인덱스에서 다른거 하나 있으면 바꿀수 없는것이다.
        result = min(result, changeCount(tops[0], tops, bottoms), changeCount(tops[0], bottoms, tops))
        result = min(result, changeCount(bottoms[0], tops, bottoms), changeCount(bottoms[0], bottoms, tops))

        # // 4가지 경우 다 아닐경우 -1로 반환
        return -1 if result == INF else result

Java

class Solution {

    final int INF = Integer.MAX_VALUE;

    public int minDominoRotations(int[] tops, int[] bottoms) {

        int result = INF;
        // top이나 bootop [0]번째 인덱스에서 다른거 하나 있으면 바꿀수 없는것이다.
        result = Math.min(result, changeCount(tops[0], tops, bottoms));
        result = Math.min(result, changeCount(tops[0], bottoms, tops));
        result = Math.min(result, changeCount(bottoms[0], tops, bottoms));
        result = Math.min(result, changeCount(bottoms[0], bottoms, tops));

        // 4가지 경우 다 아닐경우 -1로 반환
        return result == INF ? -1 : result;
    }

    public int changeCount(int value, int tops[], int bottoms[]){

        int length = tops.length;
        int count = 0;

        for (int i = 0; i < length; i++) {
            if(tops[i] != value){
                // 바꿀깞이 0번째 인덱스 값 같을 경우 바꾼다.
                if(bottoms[i] == value){
                    count++;
                } else  {
                    // 아니면 그냥 바꾼다.
                    return INF;
                }

            }
        }
        return count;
    }
}