Mock Interview: Google

914. X of a Kind in a Deck of Cards

class Solution {
    public boolean hasGroupsSizeX(int[] deck) {
        //all the numbers have the same denominator
        Map<Integer, Integer> count = new HashMap<Integer, Integer>();
        for (int i : deck) {
            count.put(i, count.getOrDefault(i, 0) + 1);
        }
        
        int denom = Integer.MAX_VALUE;
        for (int j : count.values()) {
            if (j < 2) {
                return false;
            }
            
            if (j < denom) {
                denom = j;
            }
        }
        
        for (int k : count.keySet()) {
            if (count.get(k) % denom != 0) {
                return false;
            } 
        }
        
        return true;
        
    }
}

70 / 74 test cases passed.

GCD가 아닌 그냥 가장 작은 Denominator을 구해야 하는걸 머리로는 아는데 그걸 어케해야할지 모르겠어요.....^^.....

class Solution {
    public boolean hasGroupsSizeX(int[] deck) {
        //all the numbers have the same denominator
        Map<Integer, Integer> count = new HashMap<Integer, Integer>();
        for (int i : deck) {
            count.put(i, count.getOrDefault(i, 0) + 1);
        }
        
        int denom = Integer.MAX_VALUE;
        for (int j : count.values()) {
            if (j < 2) {
                return false;
            }
            
            if (j < denom) {
                denom = j;
            }
        }
        
        boolean found = false;
        int l = 2;
        while (! found && l <= denom) {
            if (denom % l == 0) {
                denom = l; 
                found = true; 
            } else {
                l++;
            }
        }
        
        for (int k : count.keySet()) {
            if (count.get(k) % denom != 0) {
                return false;
            } 
        }
        
        return true;
        
    }
}

72 / 74 test cases passed.

제일 작은 나누는걸로 잡아주면 2개 더 패스하는데.. 별 도움이 안되네요;

루션이: Brute Force

class Solution {
    public boolean hasGroupsSizeX(int[] deck) {
        int N = deck.length;
        int[] count = new int[10000];
        for (int c: deck)
            count[c]++;

        List<Integer> values = new ArrayList();
        for (int i = 0; i < 10000; ++i)
            if (count[i] > 0)
                values.add(count[i]);

        search: for (int X = 2; X <= N; ++X)
            if (N % X == 0) {
                for (int v: values)
                    if (v % X != 0)
                        continue search;
                return true;
            }

        return false;
    }
}

Runtime: 2 ms, faster than 97.53% of Java online submissions for X of a Kind in a Deck of Cards.
Memory Usage: 39.7 MB, less than 21.39% of Java online submissions for X of a Kind in a Deck of Cards.

루션이: GCD

class Solution {
    public boolean hasGroupsSizeX(int[] deck) {
        int[] count = new int[10000];
        for (int c: deck)
            count[c]++;

        int g = -1;
        for (int i = 0; i < 10000; ++i)
            if (count[i] > 0) {
                if (g == -1)
                    g = count[i];
                else
                    g = gcd(g, count[i]);
            }

        return g >= 2;
    }

    public int gcd(int x, int y) {
        return x == 0 ? y : gcd(y%x, x);
    }
}

Runtime: 2 ms, faster than 97.53% of Java online submissions for X of a Kind in a Deck of Cards.
Memory Usage: 39.7 MB, less than 24.62% of Java online submissions for X of a Kind in a Deck of Cards.

GCD 루션이 도대체 뭐죠

1277. Count Square Submatrices with All Ones

public int countSquares(int[][] A) {
        int res = 0;
        for (int i = 0; i < A.length; ++i) {
            for (int j = 0; j < A[0].length; ++j) {
                if (A[i][j] > 0 && i > 0 && j > 0) {
                    A[i][j] = Math.min(A[i - 1][j - 1], Math.min(A[i - 1][j], A[i][j - 1])) + 1;
                }
                res += A[i][j];
            }
        }
        return res;
    }

Runtime: 5 ms, faster than 92.53% of Java online submissions for Count Square Submatrices with All Ones.
Memory Usage: 48.1 MB, less than 71.05% of Java online submissions for Count Square Submatrices with All Ones.

아래 오른쪽 코너를 잡아서 여기까지 그릴 수 있는 네모의 갯수를 세는 방식이래요

냅 다 외 워