Coding Interview

[코딩 인터뷰][LeetCode] – Evaluate Division

※ 이 포스트는 LeetCode의 코딩 인터뷰 문제 Evaluate Division에 대한 풀이입니다. 해당 풀이는 Optimal을 보장하지 않습니다.

문제 정보

문제 출처 : https://leetcode.com/problems/evaluate-division/
카테고리 : Graph, BFS
난이도 : 쉬움 ~ 중간


문제 설명

equations, values, queries가 주어질 때 다음을 리턴하시오.
equations은 리스트로 변수명의 쌍이 멤버로 주어진다. (예 : [ [“a”, “b”], [“b”, “c”] ])
이들이 나타내는 표현식은 a/b, b/c이다.

values는 equations의 표현식의 결과값을 가지고 있다.
예를 들어 values가 [2.0, 3.0]이라면, a/b = 2.0이고 b/c = 3.0이다.

queries는 리스트로 변수명의 쌍이 멤버로 주어진다. queries의 각 멤버 query에 대해
query[0] / query[1]을 출력해야한다. 예를 들어 queries가 [ [“a”, “b”], [“b”, “c”] ]) 이면 2.0, 3.0이 출력된다.
[“b”, “a”]에 대해선 0.5를 출력할 수 있겠다. 만약 값을 모른다면 -1.0을 출력한다.


문제 풀이

equations와 values로 초기 그래프를 구성할 수 있다. 예를 들어 위 자료에서는 노드 a에서 b로 향하는 가중치 2.0의 간선이 존재한다. 반대로 b에서 a로 향하는 0.5의 간선이 존재한다. 자기자신에 대해서는 1의 간선이 존재한다.

모든 정점에 대해 자신으로부터 도달할 수 있는 모든 노드를 찾고 graph를 업데이트한다. graph[src][dest]는 src/dest의 값을 가리킨다. src에서 출발해서 현재 cur에 도달한 상태에서, 다음 노드 next를 탐색한다고 가정하자.
graph[src][next] = graph[src][cur] * graph[cur][next]가 된다.

이 탐색이 끝난 후에 각 query에 대해서 graph[src][dest]를 출력하고 만약 매핑이 되어있지 않다면 -1.0을 출력한다.


코드
class Solution(object):
    def calcEquation(self, equations, values, queries):
        """
        :type equations: List[List[str]]
        :type values: List[float]
        :type queries: List[List[str]]
        :rtype: List[float]
        """
        graph = {}
        for (equation, value) in zip(equations, values):
            src, dest = equation[0], equation[1]
            if src not in graph:
                graph[src] = {}
            if dest not in graph:
                graph[dest] = {}
            graph[src][dest] = value
            graph[src][src] = 1.0
            graph[dest][src] = float(1.0) / value
            graph[dest][dest] = 1.0
        
        answer = []
        for src in graph.keys():
            visited = {src}
            q = [src]
            while len(q) > 0:
                cur = q[0]
                del q[0]
                for next_node in graph[cur].keys():
                    if next_node not in visited:
                        visited.add(next_node)
                        q.append(next_node)
                        graph[src][next_node] = graph[src][cur] * graph[cur][next_node]
                        
        for query in queries:
            src, dest = query[0], query[1]
            if src not in graph or dest not in graph[src]:
                answer.append(-1.0)
            else:
                answer.append(graph[src][dest])
        return answer
admin

Recent Posts

2024년 12월 8일 일요일 – 서울 생활 132주차

합격왕 우여곡절 끝에 드디어 합격왕에 광고를 붙였다. 서비스를 시작한지 무려 4년이 지나서야 드디어 광고를 시작하게…

2주 ago

2024년 11월 17일 일요일 – 서울 생활 129주차

괌여행 아내와 함께 괌으로 여행을 갔다. 출산 이후로 둘만 가는 첫 여행이다. 하와이가 일본인들이 많이…

1개월 ago

2024년 11월 3일 일요일 – 서울 생활 127주차

반복적인 일상 매일 아침 일어나 회사에 출근하고, 저녁을 먹고 돌아오는 일상의 반복이다. 주말은 가족을 보러…

2개월 ago

2024년 10월 6일 일요일 – 서울 생활 123주차

Planning A well-structured plan has the following characteristics:   First, the ultimate vision you aim to…

3개월 ago

2024년 9월 29일 일요일 – 서울 생활 122주차

English The most common problem for English learners like myself is that we often use…

3개월 ago

2024년 9월 22일 일요일 – 서울 생활 121주차

추석 추석을 맞아 친가 외가 처가 어르신들을 모두 뵙고 돌아왔다. 아이가 태어난지는 좀 됐지만 한국에서…

3개월 ago

This website uses cookies.