[파이썬] LeetCode 399. Evaluate Division πŸ‘‰πŸ» μˆ˜λ“€ κ°„μ˜ μˆ˜ν•™μ  관계λ₯Ό κ·Έλž˜ν”„λ‘œ ν‘œν˜„ν•˜κΈ°

Youngeui HongΒ·2023λ…„ 10μ›” 29일
0

μ•Œκ³ λ¦¬μ¦˜

λͺ©λ‘ 보기
10/12

πŸ”— 문제

LeetCode 399. Evaluate Division

πŸ‘€ μ ‘κ·Ό 방법

μˆ˜λ“€ κ°„μ˜ μˆ˜ν•™μ  κ΄€κ³„λŠ” κ·Έλž˜ν”„λ‘œ ν‘œν˜„ν•  수 μžˆλ‹€.

예λ₯Ό λ“€μ–΄ a / b = 2라 ν•œλ‹€λ©΄ aλ₯Ό 2둜 λ‚˜λˆ„λ©΄ bκ°€ 되고, bλ₯Ό 1/2둜 λ‚˜λˆ„λ©΄ aκ°€ λœλ‹€.

μ΄λŸ¬ν•œ κ΄€κ³„λŠ” μ•„λž˜μ™€ 같이 κ·Έλž˜ν”„λ‘œ ν‘œν˜„ν•  수 μžˆλ‹€. 즉 μ–΄λ–€ μˆ˜κ°€ λ‹€λ₯Έ μˆ˜κ°€ 되기 μœ„ν•΄ λ‚˜λˆ μ•Ό ν•˜λŠ” 수λ₯Ό κ°„μ„ μ˜ κ°€μ€‘μΉ˜λ‘œ μ‚ΌλŠ” 것이닀.

λ§Œμ•½ queryκ°€ ["a", "c"]둜 주어진닀면 μš°λ¦¬λŠ” a / c = ?μ—μ„œ ?의 값을 ꡬ해야 ν•œλ‹€.

이 μˆ˜μ‹μ€ a / ? = c둜 λ‹€μ‹œ ν‘œν˜„ν•  수 μžˆλŠ”λ°, 즉 aλ₯Ό μ–΄λ–€ 수둜 λ‚˜λˆ μ•Ό cκ°€ 될 수 μžˆλŠ”μ§€ κ΅¬ν•˜λŠ” 것과 λ™μΌν•œ λ¬Έμ œμ΄λ‹€.

λ”°λΌμ„œ κ·Έλž˜ν”„ μƒμ—μ„œ λ…Έλ“œ aμ—μ„œ cκΉŒμ§€ κ°€λ©΄μ„œ κ±°μΉ˜λŠ” κ°„μ„ μ˜ κ°€μ€‘μΉ˜λ₯Ό κ΅¬ν•˜λ©΄ 될 것이닀.

πŸ“ λ‹΅μ•ˆ

from collections import defaultdict


class Solution:
    def calcEquation(self, equations, values, queries):
        graph = self.buildGraph(equations, values)
        results = [self.calculatePathWeight(start, end, set(), graph) for start, end in queries]
        return results

    # equationsκ³Ό valuesλ₯Ό λ°”νƒ•μœΌλ‘œ κ·Έλž˜ν”„ 생성
    def buildGraph(self, equations, values):
        # λ”•μ…”λ„ˆλ¦¬μ˜ λ”•μ…”λ„ˆλ¦¬ ν˜•νƒœλ‘œ κ·Έλž˜ν”„ 생성
        graph = defaultdict(dict)
        # a / b = 2라면 a-> 2 -> b 그리고 b -> 1/2 -> a
        for (u, v), weight in zip(equations, values):
            graph[u][v] = weight
            graph[v][u] = 1 / weight
        return graph

    # DFS λ°©μ‹μœΌλ‘œ startμ—μ„œ endκΉŒμ§€ κ°€λŠ” 경둜의 κ°€μ€‘μΉ˜ 계산
    def calculatePathWeight(self, start, end, visited, graph):
        if start not in graph:
            return -1.0

        if end in graph[start]:
            return graph[start][end]

        visited.add(start)

        for neighbor, weight in graph[start].items():
            if neighbor not in visited:
                cumulativeWeight = self.calculatePathWeight(neighbor, end, visited, graph)
                if cumulativeWeight != -1.0:
                    return weight * cumulativeWeight

        return -1.0

0개의 λŒ“κΈ€