[Mock] Google 10

914. X of a Kind in a Deck of Cards

In a deck of cards, each card has an integer written on it.

Return true if and only if you can choose X >= 2 such that it is possible to split the entire deck into 1 or more groups of cards, where:

• Each group has exactly X cards.
• All the cards in each group have the same integer.

My Answer 1: Accepted (Runtime: 132 ms - 79.69% / Memory Usage: 14.7 MB - 28.84%)

class Solution:
    def hasGroupsSizeX(self, deck: List[int]) -> bool:
        cnt = collections.Counter(deck)
        
        mini = min(cnt.values())
        maxi = max(cnt.values())
        
        # >= 2 니까
        if mini == 1:
            return False
            
        tmp = 1
        for i in range(2, maxi+1):
            for j in cnt.values():
                if j % i != 0:
                    tmp = 0
                    break
            if tmp:
                return True
            else:
                if i == maxi:   # 마지막까지 나눠진게 없으면 False
                    return False
                tmp = 1
        
        return True

최대공약수 뭐 이런거도 생각했지만.. 다 통과가 안됨;

Counter 로 숫자들과 횟수들 구해줌

가장 적게 나온 숫자의 횟수 = mini, 가장 많이 나온 숫자의 횟수 = maxi 로 잡고
X >= 2 라고 했으니까 mini == 1 인 경우 False 처리

모든 횟수들이 2 ~ maxi 까지의 숫자로 나눠지면 그룹으로 묶이니까 True, 아니면 False
판단은 tmp 로 함 (1 이면 가능한 경우를 찾은 거고 0 이면 못 찾은 것)

---

1277. Count Square Submatrices with All Ones

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

My Answer 1: Wrong Answer (X)

<아이디어>
matrix 와 같은 크기의 arr 생성하고 값은 모두 0 으로 초기화

island 문제였나.. 그거처럼
재귀로 matrix[i][j] 와 연결된 1 들을 모두 더해서 arr[i][j] 에 넣기
(오른쪽, 아래 구역만 세주기)

예시)

matrix			arr
  [1,0,1],		  [5,0,1],
  [1,1,0],	=>	  [4,2,0],
  [1,1,0]		  [2,1,0]

arr 값들을 쭉 훑으면서 제곱수의 개수 세주면 된다고 생각...

Solution 1: Accepted (Runtime: 608 ms - 78.42% / Memory Usage: 16.4 MB - 87.37%)

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        if matrix is None or len(matrix) == 0:
            return 0
        
        rows = len(matrix)
        cols = len(matrix[0])
        
        result = 0
        
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] == 1:   
                    if r == 0 or c == 0: # Cases with first row or first col
                        result += 1      # The 1 cells are square on its own               
                    else:                # Other cells
                        cell_val = min(matrix[r-1][c-1], matrix[r][c-1], matrix[r-1][c]) + matrix[r][c]
                        result += cell_val
                        matrix[r][c] = cell_val #**memoize the updated result**
        return result 

DP 인데...

넘 어려버요

https://leetcode.com/problems/count-square-submatrices-with-all-ones/discuss/643429/Python-DP-Solution-%2B-Thinking-Process-Diagrams-(O(mn)-runtime-O(1)-space)