여행경로

문제

https://programmers.co.kr/learn/courses/30/lessons/43164#

코드

import java.util.*;

class Solution {

    void dfs(String[][] tickets, HashMap<String, ArrayList<String>> map, HashMap<String, Integer> tckt_count, ArrayList<ArrayList<String>> res, ArrayList<String> cur_arr, String cur_pos, int count){
        if(count == tickets.length){
            ArrayList<String> res_arr = new ArrayList<>();
            for(int i=0; i<cur_arr.size(); i++)
                res_arr.add(cur_arr.get(i));
            res.add(res_arr);
            return;
        }

        if(map.get(cur_pos) == null)
            return;
        for(String next_pos : map.get(cur_pos)){
            String cur_ticket = cur_pos + "," + next_pos;
            if(tckt_count.get(cur_ticket) == null || tckt_count.get(cur_ticket) <= 0)
                continue;
            tckt_count.replace(cur_ticket, tckt_count.get(cur_ticket)-1);
            cur_arr.add(next_pos);
            dfs(tickets, map, tckt_count, res, cur_arr, next_pos, count+1);
            cur_arr.remove(cur_arr.size()-1);
            tckt_count.replace(cur_ticket, tckt_count.get(cur_ticket)+1);


        }
    }

    public String[] solution(String[][] tickets) {
        String[] answer = {};
        ArrayList<ArrayList<String>> res = new ArrayList<>();
        HashMap<String, Integer> tckt_count = new HashMap<>();
        HashMap<String, ArrayList<String>> map = new HashMap<>();

        for(int i=0; i<tickets.length; i++){
            String[] ticket = tickets[i];

            String ticket_str = ticket[0] + "," + ticket[1];

            if(tckt_count.get(ticket_str) == null)
                tckt_count.put(ticket_str, 1);
            else
                tckt_count.replace(ticket_str, tckt_count.get(ticket_str)+1);

            if(map.get(ticket[0]) == null)
                map.put(ticket[0], new ArrayList<>());
            map.get(ticket[0]).add(ticket[1]);
        }

        for(String key : tckt_count.keySet())
            System.out.println(key + ", " + tckt_count.get(key));

        ArrayList<String> cur_arr = new ArrayList<>();
        cur_arr.add("ICN");
        dfs(tickets, map, tckt_count, res, cur_arr, "ICN", 0);
        System.out.println(res.size());
        Collections.sort(res, new Comparator<ArrayList<String>>(){
            @Override
            public int compare(ArrayList<String> arr1, ArrayList<String> arr2){
                for(int i=0; i<arr1.size(); i++){
                    String s1 = arr1.get(i);
                    String s2 = arr2.get(i);
                    if(s1.equals(s2) == false)
                        return s1.compareTo(s2);
                }
                return 0;
            }
        });

        answer = new String[res.get(0).size()];

        for(int i=0; i<res.get(0).size(); i++){
            answer[i] = res.get(0).get(i);
        }


        return answer;
    }
}

피드백

• 2시간 걸렸다.

  • 시행착오와 멘붕때문

• 처음에는 알파벳 순서라는 말, 그리고 공항이 10000개이기 때문에 최악의 경우 O(N^2)이 될꺼라는 생각 때문에 각 공항별로 알파벳 사전순으로 정렬하고 커서를 기억해서 결론적으로 한 번 씩만 각 티켓을 쓰도록 했다.

  • 오답이 나옴, [["AAA","BBB"], ["BBB","AAA"], ["BBB", "CCC"], ["CCC", "BBB"]] 을 생각해보라

• 이러면 완탐밖에 없네? 라는 생각에 고민을 했는데 결론적으로 맞았다...

  • 시간복잡도가 무조건 맞지 않을 수 도 있다라는 것.

• 완탐 구현중 얻은 교훈은, HashSet<String[]> 은 "값"이 아닌 "레퍼런스"를 저장한다는 것이다. 따라서 값은 리터럴을 담는 두 배열이 있을지라도 HashSet에서는 다른 것으로 판별된다.

  • 해서 String으로 concat해서 넣었다.