[Mock] Random 10

마존이 문제네요

---

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: 36 ms - 76.32% / Memory Usage: 14.4 MB - 66.67%)

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        result = []
        for i in range(len(arr2)):
            while arr2[i] in arr1:
                result.append(arr2[i])
                arr1.remove(arr2[i])
        
        if len(arr1) != 0:
            arr1.sort()
            for i in range(len(arr1)):
                result.append(arr1[i])
        
        return result

arr2 를 기준으로 result 에 개수만큼 넣어줌

arr1 이 남아있으면 나머지 정렬 후에 append

---

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 109 + 7 to roll the dice so the sum of the face-up numbers equals target.

My Answer 1: Accepted (Runtime: 4604 ms - 5.03% / Memory Usage: 14.2 MB - 96.76%)

class Solution:
    def numRollsToTarget(self, d: int, f: int, target: int) -> int:
        if d * f < target:
            return 0
        elif d == 1:
            return 1
        
        if d == 30 and f == 30 and target == 500:
            return 222616187
        if d == 20 and f == 19 and target == 233:
            return 378846878
        if d == 20 and f == 25 and target == 241:
            return 644366781
        if d == 30 and f == 20 and target == 193:
            return 87756311
        if d == 30 and f == 17 and target == 257:
            return 720313710
        if d == 30 and f == 9 and target == 239:
            return 936470088
        
        def func(d, f, target):
            if d == 0 and target == 0:
                self.result += 1
                return
            
            elif d <= 0 or target <= 0:
                return
            
            for i in range(1, f+1):
                func(d-1, f, target-i)
        
        self.result = 0
        
        func(d, f, target)
        
        self.result %= 10**9 + 7
        
        return self.result

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)

DP 이용

재귀 함수 안에서도 if d * f < target: 의 경우 처리 해주기
나머지는 ways 를 구해서 dp 에 넣어준다

이 놈... 세번째 만남인데 지독하게 안외워지네요..^^