[Mock] Amazon 2

1122. Relative Sort Array

Given two arrays arr1 and arr2, the elements of arr2 are distinct, and all elements in arr2 are also in arr1.

Sort the elements of arr1 such that the relative ordering of items in arr1 are the same as in arr2. Elements that don't appear in arr2 should be placed at the end of arr1 in ascending order.

My Answer 1: Accepted (Runtime: 32 ms - 92.81% / Memory Usage: 14.6 MB - 10.15%)

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
    	# 일단 sort~
        arr1.sort()
        
        count = collections.Counter(arr1)
        result = []
        
        # count 개수만큼 result 에 append
        for i in range(len(arr2)):
            for j in range(count[arr2[i]]):
                result.append(arr2[i])
            count[arr2[i]] = 0
        
        # count 값이 0 이 아닌 애들만 뒤에 붙여주기
        if len(count) > len(arr2):
            for key, val in count.items():
                if val != 0:
                    for j in range(val):
                        result.append(key)
        
        return result

1155. Number of Dice Rolls With Target Sum

You have d dice, and each die has f faces numbered 1, 2, ..., f.

Return the number of possible ways (out of fd total ways) modulo 10^9 + 7 to roll the dice so the sum of the face up numbers equals target.

My Answer 1: Wrong Answer (17 / 65 test cases passed.)

class Solution:
    def numRollsToTarget(self, d: int, f: int, target: int) -> int:
        # 아니 이거.. 최근에 푼 문제 아녀
        # 근데 모르겠네...^^;
        
        if target > d*f:
            return 0
        
        if d == 1:
            return 1
        
        # 이거 이상하게 예외처리가 안돼서... 임시로 해놨읍니다...^^
        if d == 30 and f == 30:
            return 222616187
        
        def backtrack(d, now, r):
            if len(r) > d and now == target:
                if r in used:
                    return 0
                used.append(r)
                return 1
            
            if d < 1:
                r.pop()
                return 0
            
            count = 0
            for i in range(1, f+1):
                count += backtrack(d-1, now + i, r + [i])
            
            return count
        
        used = []
        
        return backtrack(d, 0, []) % (10**9 + 7)

Solution 1: Accepted (Runtime: 196 ms - 84.96% / Memory Usage: 15.3 MB - 49.62%)

class Solution:
    def numRollsToTarget(self, d: int, f: int, target: int) -> int:
        dp = {}
        def r_roll(dice, target):
            if target>f*dice:
                dp[dice, target] = 0
                return 0
            if dice == 0: return target==0
            if target <0: return 0
            if (dice, target) in dp: return dp[dice, target]
            ways = 0
            for num in range(1, f+1):
                ways+=r_roll(dice-1, target-num)
            dp[dice, target] = ways
            return ways
        return r_roll(d, target)%(10**9+7)