[Mock] Random 13

마존이 문제.. 한 세번째 만남인듯...

---

1160. Find Words That Can Be Formed by Characters

You are given an array of strings words and a string chars.

A string is good if it can be formed by characters from chars (each character can only be used once).

Return the sum of lengths of all good strings in words.

My Answer 1: Accepted (Runtime: 92 ms - 88.02% / Memory Usage: 14.7 MB - 78.74%)

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        chcount = collections.Counter(chars)
        
        answer = 0
        for w in words:
            find = 0
            for i in range(len(w)):
                if w[i] in chcount and w.count(w[i]) <= chcount[w[i]]:
                    find = 1
                else:
                    find = 0
                    break
            if find:
                answer += len(w)
        
        return answer

chars 의 문자 개수들을 chcount 에 저장

words 의 단어들마다 chcount 에 있고 중복되는 문자의 개수도 맞으면(이내면) answer 에 더해주기

---

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: Time Limit Exceeded (4 / 65 Testcases Passed)

class Solution:
    def numRollsToTarget(self, d: int, f: int, target: int) -> int:
        def func(d, f, target):
            if target == 0 and d == 0:
                return 1
            
            if d*f < target or d == 0 or target < 0:
                return 0
            
            ans = 0
            for i in range(1, f+1):
                ans += func(d-1, f, target-i)
            
            return ans % (10**9 + 7)
        
        return func(d, f, target)

이거는 풀때마다 틀리는듯^^

DP 를 써야겠다는 생각은 했는데.. 범위 설정 + 어떤식으로 값을 넣을지 모르겠음..

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)

아예 나올 수 없는 수일 때)
if d*f < target => dp 값 0 & return 0
주사위를 다 썼을 때)
if d == 0 => target 도 0 이면 return 1 아니면 return 0
타겟이 음수가 됐을 때)
if target < 0 => return 0
이미 dp 에 존재하는 값일 때)
if (d, target) in dp => return dp[d, target]

무엇도 아닐 경우는 for 문으로 찾아서 dp 값 채워주기 -> 이부분은 내가 재귀로 했던 거랑 같음

★★★ dp 에는 (d, target): ways 의 형태로 넣어주기 ★★★

{(0, 5): 0, (0, 4): 0, (0, 3): 0, (0, 2): 0, (0, 1): 0,
(1, 6): 1, (1, 5): 1, (1, 4): 1, (1, 3): 1, (1, 2): 1, (1, 1): 1,
(2, 7): 6}

이제는.. 외워줄 수 있겠니..?