99클럽 TIL (240815)

> [Middler] Evaluate Division

https://leetcode.com/problems/evaluate-division/submissions/1356679117/

 

 

문제풀이 과정

이 문제를 어떻게 그래프 탐색으로 푸는지 아이디어를 생각하지 못했다. a/b에 대한 value 값이 주어지기 때문에 a -> b인 값을 value로 b -> a 인 값을 value의 역수로 설정할 수 있다. 그래서 양방향 그래프를 만든 후 dfs를 돌려 문제를 해결할 수 있다

 

💡 defaultdict()

- 파이썬에서 딕셔너리 자료형을 만드는 dict 클래스의 서브클래스로 인자로 주어지는 객체의 기본값을 딕셔너리 초기값으로 설정할 수 있다. 숫자, 리스트, 셋 등을 초기화할 수 있다. 

- 파이썬의 딕셔너리는 값이 없는 상태에서 append() 할 때 에러가 나는데 코드를 짤 때, 초기화와 값을 추가하는 작업을 함께 해야한다면 해당 메서드를 잘 사용해서 작성하면 될 것 같다.

from collections import defaultdict

list_dict = defaultdict(list) # defaultdict(<class 'list'>, {})

 

 

문제 풀이

python

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        graph = defaultdict(list)
        ans = [-1] * (len(queries)+1)
        for i, v in enumerate(equations) :
            graph[v[0]].append((v[1], values[i]))
            graph[v[1]].append((v[0], 1 / values[i]))
        
        def dfs(node, end, visited, res) :
            if node == end :
                return res
            visited.add(node)
            for i, v in graph[node] :
                if i not in visited :
                    score = dfs(i, end, visited, res * v)
                    if score != -1 :
                        return score
            return -1

        ans = []
        for i, e in enumerate(queries) :
            x, y = e
            if x not in graph or y not in graph :
                ans.append(-1)
            else :
                visited = set([])
                ans.append(dfs(x, y, visited, 1))
                
        return ans

 

시간복잡도 : O(V)

 

회고 및 느낀점

문제를 다양하게 접해보고 아이디어를 생각할 수 있는 힘을 키우자. 아직 문제를 이해하는 것이 어렵다..