[코딩테스트] 여행경로

문제

---

여행경로 문제 바로가기

제출 코드(JAVA)

---

코드 제출

import static java.util.Comparator.*;
import static java.util.stream.Collectors.groupingBy;
import java.util.*;

class Solution {
    public enum Check {
        S, F
    }

    String[] result;

    public String[] solution(String[][] tickets) {
        // 1)
        Map<String, List<String[]>> ticketsMap = Arrays.stream(tickets)
                .map(n -> {
                    return new String[]{n[0], n[1], Check.F.name()};
                })
                .collect(groupingBy(v -> v[0])); 
	// 2)
        ticketsMap.values()
                .forEach(v -> v.sort(comparing(n -> n[1])));

   	// 3)
        dfs(new String[tickets.length+1], ticketsMap, "ICN", 0);

        return result;
    }


    private int dfs(String[] tmpArry, Map<String, List<String[]>> ticketsMap, String nextPlace, int idx) {
        int result = 1;
        tmpArry[idx] = nextPlace;

        if (isLastPlace(idx, tmpArry)) {
            this.result = tmpArry;
            return -1;
        }

        for (String[] strings : ticketsMap.getOrDefault(nextPlace, new ArrayList<>())) {
            if (strings[2] == Check.F.name()){
                strings[2] = Check.S.name();
                result *= dfs(tmpArry, ticketsMap, strings[1], idx+1);
                if (result < 0) return -1;
                strings[2] = Check.F.name();
            }
        }
        return result;
    }

    private boolean isLastPlace(int idx, String[] tmpArry){
        return idx == tmpArry.length-1;
    }
}

groupingBy를 통한 출발지마다의 Map를 생성해 DFS 사용
1) map과 groupingBy를 사용해 각 출발지마다의 Map 생성 및 요소 마지막 인덱스에 탐색여부 판단할 Enum 추가
2) 도착지 기준으로 정렬
3) DFS 진행

정확성 테스트

정확성  테스트
테스트 1 〉	통과 (6.79ms, 53.9MB)
테스트 2 〉	통과 (10.26ms, 52.4MB)
테스트 3 〉	통과 (6.68ms, 52.8MB)
테스트 4 〉	통과 (6.83ms, 53.1MB)

최근 stream 공부를 병행하고 있어 stream을 활용하여 풀이 진행.
확실히 라인이 간결해진 것을 체감

제출 코드(Python)

---

코드 제출

from collections import defaultdict

def dfs(ticketsMap, answer, nextPlace, idx):
    answer[idx] = nextPlace

    if idx == len(answer)-1:
        return -1

    for p in ticketsMap[nextPlace]:
        if not p[1]:
            p[1] = True
            if dfs(ticketsMap, answer, p[0], idx+1) < 0:
                return -1
            p[1] = False
    return 1


def solution(tickets):
    answer = ["" for i in range(len(tickets)+1)]
    ticketsMap = defaultdict(lambda: []);
    for ticket in tickets:
        ticketsMap[ticket[0]].append([ticket[1], False])

    for k, v in ticketsMap.items():
        v.sort(key = lambda x : x[0])

    dfs(ticketsMap, answer, "ICN", 0)

    return answer

정확성 테스트

정확성  테스트
테스트 1 〉	통과 (0.04ms, 10.3MB)
테스트 2 〉	통과 (0.02ms, 10.3MB)
테스트 3 〉	통과 (0.02ms, 10.3MB)
테스트 4 〉	통과 (0.02ms, 10.2MB)