프로그래머스 43164번 여행경로 Java

https://school.programmers.co.kr/learn/courses/30/lessons/43164?language=java

문제

---

생각하기

---

• 그래프

• 오일러 경로

동작

결과

코드

---

import java.util.*;
import java.util.Collections;
import java.util.Objects;

class Solution {
    public List<String> solution(String[][] tickets) {
        String[] answer = {};
        
        
        int N = tickets.length;
        Arrays.sort(tickets, (o1, o2) -> {
            return o1[0].compareTo(o2[0]);
        });
                
        LinkedHashMap<String, LinkedList<String>> adjList = new LinkedHashMap<>();
        for(int i=0; i<N; i++) {
            adjList.put(tickets[i][0], new LinkedList<>());
        }
        
        
        for(int i=0; i<N; i++) {
            adjList.get(tickets[i][0]).offer(tickets[i][1]);
            Collections.sort(adjList.get(tickets[i][0]));
        }
        
        
        ArrayDeque<String> que = new ArrayDeque<>();
        List<String> list = new ArrayList<>();
        que.offer("ICN");
        
        while(!que.isEmpty()) {
            String cur = que.peekLast();
            
            if(adjList.get(cur) != null && !adjList.get(cur).isEmpty()) {
                String next = adjList.get(cur).poll();
                que.offer(next);
            } else {
                list.add(que.pollLast());
            }
        }
        

        Collections.reverse(list);        
        return list;
    } // End of solution()
} // End of Solution class

Kotlin

import java.util.*

class Solution {
    private var N = 0
    
    fun solution(tickets: Array<Array<String>>): List<String> {
        var ans = arrayOf<String>()
        
        N = tickets.size
        tickets.sortWith { o1, o2 ->
            o1[0].compareTo(o2[0])
        }
    
        
        val adjList = LinkedHashMap<String, LinkedList<String>>()
        repeat(N) { idx -> // 이 루프는 티켓의 수 N만큼 정확히 반복됩니다.
            val departure = tickets[idx][0]
            val arrival = tickets[idx][1]
            adjList.computeIfAbsent(departure) { LinkedList() }.add(arrival)
        }

        // 2. 정렬 루프
        for (list in adjList.values) { // 이 루프는 adjList에 있는 고유한 출발 공항의 수(M)만큼 반복됩니다.
            list.sort()
        }
        
        val que = ArrayDeque<String>()
        val list = ArrayList<String>()
        que.addLast("ICN")
        
        while(que.isNotEmpty()) {
            val cur = que.last()
            
            if(!adjList[cur].isNullOrEmpty()) {
                val next = adjList[cur]!!.poll()
                que.addLast(next)
            } else {
                list.add(que.pollLast())
            }
        }
        
        
        list.reverse()
        return list
    } // End of solution()
} // End of Solution class