๋‚ด ์ธ์ƒ์—์„œ ๋ฏฟ์„ ๊ฑด ์˜ค์ง ๋‚˜ ์ž์‹ ๋ฟ!

The only one you can truly trust is yourself.

๊ฒŒ์ž„ ํ”„๋กœ๊ทธ๋ž˜๋ฐ/Python ํ”„๋กœ๊ทธ๋ž˜๋ฐ

ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ์—ฌํ–‰๊ฒฝ๋กœ (๊นŠ์ด/๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰ DFS/BFS)

๐ŸŽฎinspirer9 2023. 3. 5. 13:37
728x90
๋ฐ˜์‘ํ˜•

๋ฌธ์ œ ์„ค๋ช…

์ฃผ์–ด์ง„ ํ•ญ๊ณต๊ถŒ์„ ๋ชจ๋‘ ์ด์šฉํ•˜์—ฌ ์—ฌํ–‰๊ฒฝ๋กœ๋ฅผ ์งœ๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ํ•ญ์ƒ "ICN" ๊ณตํ•ญ์—์„œ ์ถœ๋ฐœํ•ฉ๋‹ˆ๋‹ค.

ํ•ญ๊ณต๊ถŒ ์ •๋ณด๊ฐ€ ๋‹ด๊ธด 2์ฐจ์› ๋ฐฐ์—ด tickets๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ๋ฐฉ๋ฌธํ•˜๋Š” ๊ณตํ•ญ ๊ฒฝ๋กœ๋ฅผ ๋ฐฐ์—ด์— ๋‹ด์•„ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•ด์ฃผ์„ธ์š”.

์ œํ•œ ์‚ฌํ•ญ

  • ๋ชจ๋“  ๊ณตํ•ญ์€ ์•ŒํŒŒ๋ฒณ ๋Œ€๋ฌธ์ž 3๊ธ€์ž๋กœ ์ด๋ฃจ์–ด์ง‘๋‹ˆ๋‹ค.
  • ์ฃผ์–ด์ง„ ๊ณตํ•ญ ์ˆ˜๋Š” 3๊ฐœ ์ด์ƒ 10,000๊ฐœ ์ดํ•˜์ž…๋‹ˆ๋‹ค.
  • tickets์˜ ๊ฐ ํ–‰ [a, b]๋Š” a ๊ณตํ•ญ์—์„œ b ๊ณตํ•ญ์œผ๋กœ ๊ฐ€๋Š” ํ•ญ๊ณต๊ถŒ์ด ์žˆ๋‹ค๋Š” ์˜๋ฏธ์ž…๋‹ˆ๋‹ค.
  • ์ฃผ์–ด์ง„ ํ•ญ๊ณต๊ถŒ์€ ๋ชจ๋‘ ์‚ฌ์šฉํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.
  • ๋งŒ์ผ ๊ฐ€๋Šฅํ•œ ๊ฒฝ๋กœ๊ฐ€ 2๊ฐœ ์ด์ƒ์ผ ๊ฒฝ์šฐ ์•ŒํŒŒ๋ฒณ ์ˆœ์„œ๊ฐ€ ์•ž์„œ๋Š” ๊ฒฝ๋กœ๋ฅผ return ํ•ฉ๋‹ˆ๋‹ค.
  • ๋ชจ๋“  ๋„์‹œ๋ฅผ ๋ฐฉ๋ฌธํ•  ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ๋Š” ์ฃผ์–ด์ง€์ง€ ์•Š์Šต๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ

tickets return
[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]] ["ICN", "JFK", "HND", "IAD"]
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

์ž…์ถœ๋ ฅ ์˜ˆ ์„ค๋ช…

์˜ˆ์ œ #1

["ICN", "JFK", "HND", "IAD"] ์ˆœ์œผ๋กœ ๋ฐฉ๋ฌธํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์˜ˆ์ œ #2

["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] ์ˆœ์œผ๋กœ ๋ฐฉ๋ฌธํ•  ์ˆ˜๋„ ์žˆ์ง€๋งŒ ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] ๊ฐ€ ์•ŒํŒŒ๋ฒณ ์ˆœ์œผ๋กœ ์•ž์„ญ๋‹ˆ๋‹ค.

ํ’€์ด

  • ์ด ๋ฌธ์ œ๋„ ํ–‰๋ ฌ๋กœ ๋งŒ๋“ค์–ด์„œ ํ’€๋‹ค๊ฐ€ ํฌ๊ธฐํ•˜๊ณ , ๋ฏธ์‹ ์— ๊ธฐ๋Œ€๋ณด์•˜๋‹ค๊ฐ€ ๋‹ค์‹œ ํ‘ผ ๋ฌธ์ œ... ใ…ก.ใ…ก;
  • ๋ฏธ์‹ ์˜ ํ”์ ์ด ์žˆ๋‹ค. random.seed(43164) ใ…‹ใ…‹
import random
random.seed(43164)
    
def solution(tickets):
    answer = []
    stack = []
    graph = {}
    
    for a, b in tickets:
        try:
            graph[a].append(b)
        except:
            graph[a] = [b]
    
    for a, b in graph.items():
        graph[a].sort(reverse=True)
    
    stack = ["ICN"]
    
    while stack:
        #print("graph:", graph)
        
        a = stack.pop()
        #print("stack:", stack)
        
        if a in graph and len(graph[a]) != 0:
            stack.append(a)
            stack.append(graph[a].pop())
            if len(graph[a]) == 0:
                del graph[a]
        else:
            answer.append(a)
            
        #print("stack:", stack)
        #print("graph:", graph)
        #print("answer:", answer)
    answer.reverse()

    return answer
  • ๊ณ ์ˆ˜์˜ ์ฝ”๋“œ
    • ์—„์ฒญ ๊ฐ„๋‹จํ•˜๋‹ค.
from collections import defaultdict
def solution(tickets):
    r = defaultdict(list)
    for i,j in tickets:
        r[i].append(j)
    for i in r.keys():
        r[i].sort()

    s = ["ICN"]
    p = []
    while s:
        q = s[-1]
        if r[q] != []:
            s.append(r[q].pop(0))
        else:
            p.append(s.pop())
    return p[::-1]
728x90
๋ฐ˜์‘ํ˜•