[LeetCode] 332 - Reconstruct Itinerary(java)

https://leetcode.com/problems/reconstruct-itinerary/

LeetCode - The World's Leading Online Programming Learning Platform

이 문제와 거의 유사한 문제를 프로그래머스에서 풀었던 기억이 난다.

그때도 dfs를 사용하여 풀었다.

 

핵심

문제 자체는 되게 단순하다. List에 시작점, 도착점을 저장해 둔 상태인데, 계속해서 이어나가면 된다.

단 정답의 개수가 여러 개가 나올 수 있는데, 이때 사전순으로 가장 처음 오는 것을 정답으로 해야 한다.

이때 모든 경우를 모두 탐색하면 시간 초과가 발생한다.

 

정답 코드 1

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

class Solution {
    private boolean[] visited;
    private List<String> results;

    public List<String> findItinerary(List<List<String>> tickets) {
        visited = new boolean[tickets.size()];
        results = new ArrayList<>();

        tickets.sort((list1, list2) -> {
            for (int i = 0; i < Math.min(list1.size(), list2.size()); i++) {
                int comparison = list1.get(i).compareTo(list2.get(i));
                if (comparison != 0) {
                    return comparison;
                }
            }
            return Integer.compare(list1.size(), list2.size());
        });

        dfs(tickets, "JFK", 0);

        return Arrays.stream(results.get(0).split(" ")).collect(Collectors.toList());
    }

    private void dfs(List<List<String>> tickets, String now, int useTicketCount) {
        if (!results.isEmpty()){
            return;
        }
        if (useTicketCount == tickets.size()) {
            results.add(now);
            return;
        }

        for (int i = 0; i < tickets.size(); i++) {
            if (!visited[i] && now.substring(now.length() - 3).equals(tickets.get(i).get(0))) {
                visited[i] = true;
                dfs(tickets, now + " " + tickets.get(i).get(1), useTicketCount + 1);
                visited[i] = false;
            }
        }
    }
}

해설

방문한 곳은 다시 탐색하면 안 된다. 따라서 visited를 사용하였다.

모든 경우를 탐색하면 시간초과가 발생하기에 정렬을 통해 가장 먼저 탐색되는 것을 답으로 선택하기로 하였다.

따라서 dfs 메서드를 보면 result에 답이 이미 담긴 경우 return을 통해 나머지 작업은 그냥 수행하지 않는다.

나머지 연산은 문제의 조건대로 이름이 이어지는 경우 dfs를 통해 추가한다.

 

 

정답 코드 2

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, PriorityQueue<String>> graph = new HashMap<>();

        for (List<String> ticket : tickets) {
            graph.computeIfAbsent(ticket.get(0), k -> new PriorityQueue<>()).add(ticket.get(1));
        }

        LinkedList<String> stack = new LinkedList<>();
        stack.add("JFK");
        LinkedList<String> result = new LinkedList<>();

        while (!stack.isEmpty()) {
            while (!graph.getOrDefault(stack.peekLast(), new PriorityQueue<>()).isEmpty()) {
                stack.add(graph.get(stack.peekLast()).poll());
            }
            result.addFirst(stack.pollLast());
        }

        return result;
    }
}

해설

Map에 출발점, pq(도착점) 형식으로 만들어주었다.

map의 value인 우선순위큐에 값을 넣어주는데, 만약 키가 없을 경우 새로운 pq를 생성해야 하기에 computeIfAbsent를 사용하였다.

computeIfAbsent는 키값이 없을 경우 뒤 람다식을 실행한다.

이후 문제의 조건대로 이름을 이어 붙인다.

pq를 사용하기에 무조건 이름이 빠른 순으로 담게 된다.

 

 

배운 점

당연하게 dfs로 풀려했다. 이미 풀었던 문제와 매우 유사하여 다른 방법은 생각을 하지 않았다.

다른 정답 코드를 보면 코드도 단순하고 매우 논리적으로 풀었다는 생각이 든다.

항상 더 쉽거나 다른 풀이도 생각하는 습관을 들이자.