[テストコード/プログラマー]旅行コース


💡の意見を打診
  • 枚のチケットをセットでデックに入れます.
  • は、ICNを最初に変数に格納する.
  • Dequeから1つ取り出し,出発地が変数と同一か否かを判断する.
  • が同じであれば、その変数で始まる複数のアルファベット順がより高いか否かを判断する.
  • でない場合はdequeを再入れ、正しい場合は変数にその到着地を保存し、解答配列にその到着地を追加する.
  • Deque祈願まで繰り返します.
  • 他人のコード
    コードを書くのは難しくて、時間が経つのが速すぎて、他の人のコードを見ることにしました.
    🔗コメント
    https://gurumee92.tistory.com/165
    def solution(tickets):
        # 1. 그래프 생성
        routes = dict()
    
        for (start, end) in tickets:
            routes[start] = routes.get(start, []) + [end]  
    
        # 2. 시작점 - [끝점] 역순으로 정렬    
        for r in routes.keys():
            routes[r].sort(reverse=True)
    
        # 3. DFS 알고리즘으로 path를 만들어줌.
        st = ["ICN"]
        path = []
        
        while st:
            top = st[-1]
    
            if top not in routes or len(routes[top]) == 0:
                path.append(st.pop())
            else:
                st.append(routes[top][-1])
                routes[top] = routes[top][:-1]
        
        # 4. 만든 path를 거꾸로 돌림.
        answer = path[::-1]
        return answer
  • (始点-[終点])のペアのグラフィックを作成します.
  • 到着点のリストは、
  • を逆順に配列する.
  • DFSアルゴリズムによってすべての点を巡回する.
    3-1. 問題条件に応じて、まず「ICN」をスタックに入れます.
    3-2. スタックが解放されるまで繰り返します.
    (1). スタックから一番上のストレージデータtopを取り出します.
    (2). topがグラフィックにない場合、またはtopを起点とするチケットがない場合は、スタックからpathに取り出して保存します.
    (3). (2)番号でない場合はtopを起点とする端点から最後の点を取り出してスタックに保存する.
  • のようにして得られたpathは逆順に配列される.
  • 🔗プログラマー-旅行コース
    https://programmers.co.kr/learn/courses/30/lessons/43164