[LeetCode] - 1436. Destination City

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Destination City" 문제입니다.

--> https://leetcode.com/problems/destination-city/description/

 

문제 : 

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.

---

Example 1 :

Input : paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]

Output : "Sao Paulo" Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of : "London" -> "New York" -> "Lima" -> "Sao Paulo".

 

Example 2 :

Input : paths = [["B","C"],["D","B"],["C","A"]]

Output : "A"

Explanation : All possible trips are: "D" -> "B" -> "C" -> "A". "B" -> "C" -> "A". "C" -> "A". "A".

Clearly the destination city is "A".

 

Example 3 :

Input : paths = [["A","Z"]]

Output : "Z"

 

Constraints :

• 1 <= paths.length <= 100
• paths[i].length == 2
• 1 <= cityAi.length, cityBi.length <= 10
• cityAi != cityBi
• All strings consist of lowercase and uppercase English letters and the space character.

---

이 문제는 주어진 경로 배열 paths에서 출발지와 도착지가 주어졌을 때, 도착지를 반환하는 문제입니다. 도착지는 다른 도시로 가는 경로가 없는 도시입니다. 경로가 선형으로 연결되어 있으며, 루프가 없다는 점이 보장됩니다.

class Solution {
    public String destCity(List<List<String>> paths) {
        Map<String, String> cityMap = new HashMap<>();
        for (List<String> path : paths) {
            cityMap.put(path.get(0), path.get(1)); // departure -> destination
        }

        String start = paths.get(0).get(0);
        while (cityMap.containsKey(start)) {
            start = cityMap.get(start);
        }

        return start;
    }
}

 

이 코드는 주어진 경로 목록을 사용하여 최종 도착지를 찾습니다. 주어진 경로는 선형으로 연결되어 있으며 루프가 없다는 보장이 있기 때문에, 출발지에서 시작하여 연속적으로 이동하면 최종 도착지에 도달할 수 있습니다.

1. 경로 맵 생성 :
   • cityMap이라는 HashMap을 사용하여 각 출발지를 키로 하고 해당 도착지를 값으로 저장합니다.
2. 최종 도착지 찾기 :
   • paths의 첫 번째 경로의 출발지에서 시작합니다.
   • cityMap을 사용하여 현재 도시의 도착지를 찾아 계속 이동합니다.
   • 더 이상 이동할 수 없는 도시가 최종 도착지입니다.

• 시간 복잡도 : O(n)
  • 경로를 cityMap에 추가하는 작업은 O(n) 시간이 소요됩니다. 여기서 n은 경로의 수입니다.
  • 최종 도착지를 찾기 위해 경로를 따라 이동하는 작업도 O(n) 시간이 소요됩니다.
  • 따라서 전체 시간 복잡도는 O(n)입니다.

• 공간 복잡도 : O(n)
  • cityMap은 경로 수에 비례하는 크기의 공간을 사용합니다.
  • 따라서 전체 공간 복잡도는 O(n)입니다.

---

내 코드 Runtime 결