1436. Destination City

문제

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

풀이

class Solution {
    public String destCity(List<List<String>> paths) {
        Set<String> start = new HashSet<>();

        for(List<String> list : paths) {
            start.add(list.get(0));
        }

        for(int i = 0; i < paths.size(); i++) {
            for(int j = 0; j < paths.get(0).size(); j++) {
                if(!start.contains(paths.get(i).get(j))) {
                    return paths.get(i).get(j);
                }
            }
        }
        return "good";
    }
}

• 목적지와 출발지로 구분을 해야하는데, 최종 목적지는 단 한번도 출발지에 들어가면 안됨
• list의 0번째만 출발지이므로, start set에 저장
• 배열을 돌면서 start set에 있는지 확인, 없다면 최종 목적지이므로 반환
  • 내부 도착지 루프는 paths.get(i).size() = 2로 고정되어 있기 때문에
    중첩 for문이 있어도 전체 시간 복잡도는 O(2N) = O(N)