number dictionary 선언시…

나는 여태껏 python dictionary를 사용할 때, key값이 어떤 값이던간에 key:value 형태로 사용하곤 했다.

key 값이 숫자건 문자건

• key가 생성되어 있다면 value를 추가(혹은 수정)
• key가 없다면 key에 대해 정의한뒤 value를 추가

하는 식으로 말이다.

(defaultDict 안쓰는 고집이 있다.)

 

가령 예를 들어, 무방향 그래프에서 각 노드 간 연결이 아래와 같이 주어진다고 할 때

connections = [[0,1],[0,2],[1,2]]

이걸 dictionary 형태로 구성한다면

connections = [[0,1],[0,2],[1,2]]

num_dict = {}
for conn in connections:
    a,b = conn[0], conn[1]
    if a not in num_dict:
        num_dict[a] = []
    num_dict[a].append(b)
    
    if b not in num_dict:
        num_dict[b] = []
    num_dict[b].append(a)

print(num_dict)
// {0: [1, 2], 1: [0, 2], 2: [0, 1]}

위와 같이 표현할 수 있다.

이번에 알고리즘을 풀면서 평소와 같이 위처럼 구성한 뒤, 문제를 풀었는데...

https://leetcode.com/problems/number-of-operations-to-make-network-connected/

Number of Operations to Make Network Connected - LeetCode

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if len(connections) < n-1:
            return -1
        
        num_dict = {}
        for conn in connections:
            a, b = conn[0], conn[1]
            if a not in num_dict:
                num_dict[a] = []
            num_dict[a].append(b)
            if b not in num_dict:
                num_dict[b] = []
            num_dict[b].append(a)
        
        visited = set()
        def dfs(num):
            if num not in num_dict:
                return [num]
            answer = [num]
            visited.add(num)
            nums = num_dict[num]
            for k in nums:
                if k in visited:
                    continue
                visited.add(k)
                answer.extend(dfs(k))
            return answer

        answer = [dfs(k) for k in range(n) if k not in visited]
        return len(answer)-1

속도가 느린 걸 보고...

다른 사람의 코드를 둘러보던 중 정말 신박한 number dictionary 구성을 확인했다.

 

코드는 아래와 같다.

graph = [set() for i in range(n)]
for u, v in connections:
    graph[u].add(v)
    graph[v].add(u)

key값이 숫자라면(더불어 index로 접근이 가능하다면…!) list로 만들고

해당 배열 공간에 필요로 하는 자료구조를 선언…

(아니 완전 깔끔하고… 알아보기도 쉽잖아…?)

 

 

마침 다음날 문제 역시 number dictionary 구성이 필요하길래 위 코드처럼 구성한 뒤 문제를 풀어보았다.

https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/

Reorder Routes to Make All Paths Lead to the City Zero - LeetCode

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:

        roads = [dict() for i in range(n)]
        for conn in connections:
            a,b = conn[0], conn[1]
            roads[a][b] = "out"
            roads[b][a] = "in"

        visited = set()
        def dfs(num):
            if num in visited:
                return 0
            total = 0 
            num_dict = roads[num]
            visited.add(num)
            for key, val in num_dict.items():
                if key not in visited:
                    if val == "out":
                        total += 1
                    total += dfs(key)
            return total
        return dfs(0)

 

속도의 경우 dictionary의 key를 쓰나, list의 index로 구성을 하나 똑같이 O(1)의 속도이기 때문에 상관은 없을 걸로 보이나...

다만 주의할 점으로는 기존의 dictionary 구조로 구성한다면 문제에 등장하는 key값만 선언이 가능하기 때문에

등장하지 않는 key도 index로 구성 + 각 index 별로 별도의 자료구조가 들어가 있어서 메모리 적인 측면에서 손해가 생긴다.

 

 

무튼 신기하게 만드는 거 보고 정리~