[LeetCode] 1436. Destination City [Python] 해시셋

 

leetcode.com/problems/destination-city/

Destination City - LeetCode

You are given the array paths, where paths[i] = [cityAi, cityBi] means there exists a direct path going from cityAi to cityBi. Return the destination city, that is, the city without any path outgoing to another city.

It is guaranteed that the graph of paths forms a line without any loop, therefore, there will be exactly one destination city.

 

이 문제는 그래프에서 sink를 찾는 문제이다. 주어진 paths에서 출발지와 도착지를 확인하고, 최종 목적지를 찾아내는 문제이다. 문제에도 나와있듯, 그래프에 싸이클이 없고, 반드시 한 개의 도착지, 즉 싱크가 존재한다. 문제상에 이미 '단 한 개의 도착지'라고 나와있기 때문에, 굳이 어느 시티에서 갈 수 있는 시티는 무엇 무엇이 있는 정보는 필요가 없다. 즉, indegree와 outdegree를 일일이 기록할 필요 없이, 출발지와 도착지의 리스트만 체크해주면 된다.

---

class Solution:
    def destCity(self, paths: List[List[str]]) -> str:
        src = set()
        des = set()
        for s, d in paths:
            src.add(s)
            des.add(d)
        for i in des:
            if i not in src: return i

---

src에는 paths에 있는 출발지를 저장시키고, des에는 paths에 있는 도착지를 저장시킨다. des에는 있고 src는 없다는 이야기는 그 시티가 sink라는 이야기이기때문에, des에 저장된 시티들 중에 src에 없는 시티를 찾아 리턴 시키면 된다. 해당 솔루션의 시간 복잡도는 O(n)이며 공간 복잡도 역시 O(n)가 나온다.