[Mock] Google 11

1089. Duplicate Zeros

Given a fixed length array arr of integers, duplicate each occurrence of zero, shifting the remaining elements to the right.

Note that elements beyond the length of the original array are not written.

Do the above modifications to the input array in place, do not return anything from your function.

My Answer 1: Accepted (Runtime: 72 ms - 64.97% / Memory Usage: 14.8 MB - 62.57%)

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        i = 0
        while i < len(arr):
            if arr[i] == 0:
                arr.pop()
                arr.insert(i, 0)
                i += 1
            i += 1

맨 끝에 pop 해주고 0 넣기

My Answer 2: Accepted (Runtime: 492 ms - 18.98% / Memory Usage: 15.1 MB - 8.75%)

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        i = 0
        while i < len(arr):
            if arr[i] == 0:
                arr[:] = arr[:i] + [0] + arr[i:len(arr)-1]
                i += 1
            i += 1

arr 을 slicing 해서 중간에 0 넣기

arr = arr[:i] + [0] + arr[i:len(arr)-1] 이렇게만 쓰면 안된다
꼭 arr[:] 써주기!!!

Solution 1: Accepted (Runtime: 72 ms - 64.97% / Memory Usage: 15 MB - 31.08%)

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        zeroes = arr.count(0)
        n = len(arr)
        for i in range(n-1, -1, -1):
            if i + zeroes < n:
                arr[i + zeroes] = arr[i]
            if arr[i] == 0: 
                zeroes -= 1
                if i + zeroes < n:
                    arr[i + zeroes] = 0

근데 in place 로 하려면 이렇게 해야하는듯..

0 의 개수를 세주고 arr 을 거꾸로 확인하면서 숫자들을 미리 zeroes 만큼 이동시킴
=> arr[i + zeroes] = arr[i]

0 을 만나면 zeroes -= 1 & arr[i + zeroes] = 0 로 0 추가

예시)

input: [1,0,2,3,0,4,5,0]

[1, 0, 2, 3, 0, 4, 5, 4]   i = 5, zeroes = 2, 첫번째 if
[1, 0, 2, 3, 0, 4, 0, 4]   i = 4, zeroes = 2, 첫번째 if
[1, 0, 2, 3, 0, 0, 0, 4]   i = 4, zeroes = 1, 두번째 if
[1, 0, 2, 3, 3, 0, 0, 4]   i = 3, zeroes = 1, 첫번째 if
[1, 0, 2, 2, 3, 0, 0, 4]   i = 2, zeroes = 1, 첫번째 if
[1, 0, 0, 2, 3, 0, 0, 4]   i = 1, zeroes = 1, 첫번째 if
[1, 0, 0, 2, 3, 0, 0, 4]   i = 1, zeroes = 0, 두번째 if
[1, 0, 0, 2, 3, 0, 0, 4]   i = 0, zeroes = 0, 첫번째 if

---

1007. Minimum Domino Rotations For Equal Row

In a row of dominoes, tops[i] and bottoms[i] represent the top and bottom halves of the ith domino. (A domino is a tile with two numbers from 1 to 6 - one on each half of the tile.)

We may rotate the ith domino, so that tops[i] and bottoms[i] swap values.

Return the minimum number of rotations so that all the values in tops are the same, or all the values in bottoms are the same.

If it cannot be done, return -1.

My Answer 1: Accepted (Runtime: 1088 ms - 80.86% / Memory Usage: 15.2 MB - 69.09%)

class Solution:
    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
        count = collections.Counter(tops) + collections.Counter(bottoms)
        
        key = -1
        for k, v in count.items():
            if v >= len(tops) and v == max(count.values()):
                key = k
                break
        
        if key == -1:
            return -1
        
        rotate = 0  # 0: top 으로 몰빵, 1: bottom 으로 몰빵
        
        if tops.count(key) < bottoms.count(key):
            rotate = 1
        
        ans = 0
        for t, b in zip(tops, bottoms):
            if t != key and b != key:
                return -1
            if rotate == 0 and b == key and t != b:
                ans += 1
            elif rotate and t == key and t != b:
                ans += 1
        
        return ans

1. 전체 숫자 중에 가장 많이 나오는 숫자 찾기 (전체 길이 이상의 빈도수 & 최댓값)
   => if v >= len(tops) and v == max(count.values()):

2. 전체 길이 이상의 빈도수가 없으면 row 가 모두 같아질 수 없으므로 return -1

3. 찾은 key 값이 각 row 에서 몇번 나오는지 확인해서 더 적게 rotate 할 기준 row 잡기

4. rotate 횟수 세주기

tops 값과 bottoms 값이 같을 때를 따로 세주고 rotate 횟수 계산할 때 빼줘도 됨