LeetCode - 1436. Destination City

Solution

var destCity = function(paths) {
    const hash = {}

    for(path of paths) {
        hash[path[0]] ? hash[path[0]] += 1 : hash[path[0]] = 1
        hash[path[1]] ? hash[path[1]] -= 1 : hash[path[1]] = -1
    }

    for(key in hash) {
        if(hash[key] === -1) return key
    }
};

Explanation

최종 목적지를 구하는 문제이다.
문제에서 가장 중요한 포인트는 도시간 연결 경로를 그래프로 표현하면 선형적이라는 것이다. 즉, 최종 목적지는 반드시 하나라는 것이다.

그러면 도시는 세 종류로 나뉠 수 있다.
1. 나가는 경로만 있는 도시
2. 들어오고 나가는 경로 둘 다 있는 도시
3. 들어오는 경로만 있는 도시

그렇다면 3번째 종류의 도시가 최종 목적지가 된다. 각 도시별 종류를 확인하기 위해서 Hash Table을 만드는데 아래와 같은 법칙을 적용한다.

• 특정 도시에서 나가는 경로가 존재할 경우 +1
• 특정 도시로 들어오는 경로가 존재할 경우 -1

도시의 종류는 다음과 같이 판별할 수 있다.
1. 나가는 경로만 있는 도시 = 1
2. 들어오고 나가는 경로 둘 다 있는 도시 = 0
3. 들어오는 경로만 있는 도시 = -1
그러면 만들어진 Hash Table에서 값이 -1인 도시를 찾아서 리턴하면 된다.