Skip to main content

1007 - Minimum Domino Rotations For Equal Row

info

풀이 키워드​

스포주의

그리디


풀이 코드​

info
  • 메모리: 50200 KB
  • 시간: 5 ms
class Solution {
    int[] topCnt;
    int[] bottomCnt;
    int[] equalCnt;
    int n;

    public int minDominoRotations(int[] tops, int[] bottoms) {
        n = tops.length;
        topCnt = new int[7]; // count 1 ~ 6
        bottomCnt = new int[7];
        equalCnt = new int[7];

        for (int i = 0; i < n; ++i) {
            ++topCnt[tops[i]];
            ++bottomCnt[bottoms[i]];
            if (tops[i] == bottoms[i]) ++equalCnt[tops[i]];
        }

        int ans = 20000;
        for (int k = 1; k < 7; ++k) {
            if (n <= topCnt[k] + bottomCnt[k] - equalCnt[k]) {
                int swapCnt = n - Math.max(topCnt[k], bottomCnt[k]);
                ans = swapCnt < ans ? swapCnt : ans;
            }
        }
        if (ans == 20000) return -1;
        return ans;
    }
}

풀이 해설​

O(n)의 시간복잡도로 풀이할 수 있다.

2≤n≤2×1042 \le n \le 2 \times 10^4 이므로 DP일리는 없는 문제.


문제를 접했을때 다음의 2가지 사항이 떠올랐다.

  1. 도미노 값(1~6)을 k라고 할 때, k는 swap해서 정답 조건이 될 수 있는 값인가?
  2. 될 수 있다면 swap 횟수 값을 어떻게 도출할 수 있는가?

📌 k에 대한 분리된 카운팅​

정답 후보가 되는 경우는 swap 해서 k값이 한 줄에 n개가 될 수 있음을 가정하므로

tops와 bottoms의 k값을 각각 카운팅할 필요가 있다.


📌 coner case 처리​

다만, 정답 조건 가능 여부를 n <= topCnt[k] + bottomCnt[k] 로 판단해버리면

tops와 bottoms가 모두 k값인 경우에 실제로는 swap이 무효해도 중복 카운팅되어 잘못 판단할 수 있다.

따라서 무효한 swap 횟수를 해당 조건에서 차감해주기 위해 equalCnt를 추가 연산했다.


메모​

  • 어렵진 않았는데 corner case 매우 주의.