> [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)
회고 및 느낀점
문제를 다양하게 접해보고 아이디어를 생각할 수 있는 힘을 키우자. 아직 문제를 이해하는 것이 어렵다..
'TIL' 카테고리의 다른 글
99클럽 TIL (240817) (0) | 2024.08.17 |
---|---|
99클럽 TIL (240816) (0) | 2024.08.16 |
99클럽 TIL (240814) (0) | 2024.08.14 |
99클럽 TIL (240813) (0) | 2024.08.13 |
99클럽 TIL (240812) (0) | 2024.08.12 |