[Mock] Random 23

---

1079. Letter Tile Possibilities

You have n tiles, where each tile has one letter tiles[i] printed on it.

Return the number of possible non-empty sequences of letters you can make using the letters printed on those tiles.

My Answer 1: Accepted (Runtime: 124 ms - 49.52% / Memory Usage: 17.4 MB - 38.39%)

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        def func(s, comb):
            self.comb.add(comb)
            
            if len(s) == 0:
                return
            
            for i in range(len(s)):
                func(s[:i]+s[i+1:], comb+s[i])
        
        self.comb = set()
        func(tiles, "")
        
        self.comb = list(self.comb)
        
        return len(self.comb) - 1

모든 조합이 만들어질 때마다 self.comb 에 넣어주기

"" 빈 문자열의 조합도 들어가기 때문에 전체 길이 - 1 return

---

1042. Flower Planting With No Adjacent

You have n gardens, labeled from 1 to n, and an array paths where paths[i] = [xi, yi] describes a bidirectional path between garden xi to garden yi. In each garden, you want to plant one of 4 types of flowers.

All gardens have at most 3 paths coming into or leaving it.

Your task is to choose a flower type for each garden such that, for any two gardens connected by a path, they have different types of flowers.

Return any such a choice as an array answer, where answer[i] is the type of flower planted in the (i+1)th garden. The flower types are denoted 1, 2, 3, or 4. It is guaranteed an answer exists.

My Answer 1: Accepted (Runtime: 476 ms - 36.34% / Memory Usage: 21.4 MB - 29.07%)

class Solution:
    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
        dic = {i+1:[] for i in range(n)}
        for i in range(len(paths)):
            dic[paths[i][0]].append(paths[i][1])
            dic[paths[i][1]].append(paths[i][0])
        
        ans = [0]*(n)
        
        for i in range(n):
            ans[i] = 1
            while ans[i] in dic[i+1]:
                ans[i] += 1
            for j in range(len(dic[i+1])):
                if i+1 in dic[dic[i+1][j]]:
                    dic[dic[i+1][j]].remove(i+1)
                    dic[dic[i+1][j]].append(ans[i])
        
        return ans

우선 각 정원과 이웃한 정원들을 모두 dic 에 저장

정원은 1 ~ n 으로 정해져있으므로 순서대로 보면서 ans 값을 1 로 초기화

현재 ans 값이 이웃한 정원 중에 있으면 1 씩 늘려가면서 이웃하지 않은 숫자 찾기

숫자가 정해졌으면 지금 정원과 연결된 정원들의 dic 값을 update

=> 현재 값 대신 정해진 ans 값으로 바꿈

Solution 1: Accepted (Runtime: 420 ms - 91.23% / Memory Usage: 21 MB - 87.22%)

class Solution:
    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
        res = [0] * n
        G = [[] for i in range(n)]
        for x, y in paths:
            G[x - 1].append(y - 1)
            G[y - 1].append(x - 1)
        for i in range(n):
            res[i] = ({1, 2, 3, 4} - {res[j] for j in G[i]}).pop()
        return res

비슷한데 더 빠르게 할 수 있다

G 에는 이웃인 정원들을 넣어주고

결과값은 꽃의 타입이 총 4 가지 이므로
{1, 2, 3, 4} 중에서 이웃한 값들만 빼준 후 값 하나만 pop 하면 됨