컴닥
2020. 10. 12. 14:48
반응형
배달
Summer/Winter Coding(~2018)
768명 완료
https://programmers.co.kr/learn/courses/30/lessons/12978
코딩테스트 연습 - 배달
5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4
programmers.co.kr
다익스트라 알고리듬을 이용하는 거 같은데..
다익스트라 알고리듬이 기억이 안 난다 ㅠ,.ㅠ
일단 생각의 흐름을 따라 코딩했다..
테스트 케이스는 통과가 되지만...
당연히 순서가 꼬이면... 엉망인 답이 나온다..
문제는 순서~!
def solution(n, road, k):
distances = {1: 0}
for index, (a, b, length) in enumerate(road):
distances[b] = min(distances.get(a, float('inf')) + length, distances.get(b, float('inf')))
distances[a] = min(distances[b] + length, distances.get(a, float('inf')))
# print(distances)
return len([1 for a in distances.values() if a <= k])
print(solution(5, [[1, 2, 1], [2, 3, 3], [5, 2, 2], [1, 4, 2], [5, 3, 1], [5, 4, 2]], 3))
print(solution(5, [[2, 3, 3], [5, 2, 2], [1, 4, 2], [5, 3, 1], [5, 4, 2], [1, 2, 1]], 3)){1: 0, 2: 1}
{1: 0, 2: 1, 3: 4}
{1: 0, 2: 1, 3: 4, 5: 3}
{1: 0, 2: 1, 3: 4, 5: 3, 4: 2}
{1: 0, 2: 1, 3: 4, 5: 3, 4: 2}
{1: 0, 2: 1, 3: 4, 5: 3, 4: 2}
4
{1: 0, 3: 2000, 2: 2000}
{1: 0, 3: 2000, 2: 2000, 5: 2000}
{1: 0, 3: 2000, 2: 2000, 5: 2000, 4: 2}
{1: 0, 3: 2000, 2: 2000, 5: 2000, 4: 2}
{1: 0, 3: 2000, 2: 2000, 5: 4, 4: 2}
{1: 0, 3: 2000, 2: 1, 5: 4, 4: 2}
3다익스트라가 가까운 노드부터 탐색하던 개념이던가...
예전에 책에서 본 적 있는데...
알고리듬 책은 Hello Coding 그림으로 개념을 이해하는 알고리즘 - 아디트야 바르가바 추천.
고등학교 때 퀵 정렬 공부한 이후로 전혀 알고리듬을 공부하지 않았던 아재 취미 코더에게도 어렵지 않았다...
(뒷광고 아님, 리뷰용 책 한 권 받아본 적 없음.)
def solution(n, road, k):
graph = {}
for a, b, cost in road:
graph[a] = graph.get(a, set()).union({(b, cost)})
graph[b] = graph.get(b, set()).union({(a, cost)})
distances = {1: 0}
while graph:
node, min_val = None, float('inf')
for key in distances:
if key in graph and distances[key] < min_val:
node, min_val = key, distances[key]
for neighbor, cost in graph[node]:
if neighbor in graph:
distances[neighbor] = min(distances[node] + cost, distances.get(neighbor, float('inf')))
del graph[node]
return sum(1 for a in distances.values() if a <= k)테스트 1 〉 통과 (0.07ms, 10.9MB)
테스트 2 〉 통과 (0.06ms, 10.7MB)
테스트 3 〉 통과 (0.07ms, 10.8MB)
테스트 4 〉 통과 (0.08ms, 10.7MB)
테스트 5 〉 통과 (0.09ms, 10.8MB)
테스트 6 〉 통과 (0.05ms, 10.7MB)
테스트 7 〉 통과 (0.07ms, 10.8MB)
테스트 8 〉 통과 (0.06ms, 10.8MB)
테스트 9 〉 통과 (0.06ms, 10.9MB)
테스트 10 〉 통과 (0.07ms, 10.8MB)
테스트 11 〉 통과 (0.07ms, 10.8MB)
테스트 12 〉 통과 (0.17ms, 10.7MB)
테스트 13 〉 통과 (0.12ms, 10.7MB)
테스트 14 〉 통과 (3.02ms, 11.2MB)
테스트 15 〉 통과 (4.55ms, 11.6MB)
테스트 16 〉 통과 (0.09ms, 10.8MB)
테스트 17 〉 통과 (0.12ms, 10.8MB)
테스트 18 〉 통과 (0.69ms, 10.9MB)
테스트 19 〉 통과 (3.46ms, 11.5MB)
테스트 20 〉 통과 (0.62ms, 10.8MB)
테스트 21 〉 통과 (5.58ms, 12.4MB)
테스트 22 〉 통과 (0.91ms, 10.9MB)
테스트 23 〉 통과 (4.82ms, 12MB)
테스트 24 〉 통과 (2.97ms, 11.4MB)
테스트 25 〉 통과 (7.16ms, 13.3MB)
테스트 26 〉 통과 (6.91ms, 13.3MB)
테스트 27 〉 통과 (7.17ms, 13.5MB)
테스트 28 〉 통과 (7.55ms, 13.6MB)
테스트 29 〉 통과 (7.29ms, 13.5MB)
테스트 30 〉 통과 (5.63ms, 13.5MB)
테스트 31 〉 통과 (0.18ms, 10.8MB)
테스트 32 〉 통과 (0.25ms, 10.8MB)생각의 흐름에 따라 코딩했더니..
일반적인 다익스트라 스타일과 좀 다른 느낌이라..
공부 차원에서...
일반적인 다익스트라 스타일도...
찾아서 코딩해 보았다...
def solution(N, road, K):
from queue import PriorityQueue
distances = [float('inf') for _ in range(N + 1)]
distances[1] = 0
que = PriorityQueue()
que.put((0, 1))
while not que.empty():
distance, node = que.get()
if distance > distances[node]: # 없어도 작동은 하지만.. 속도를 위해..
continue
for a, b, cost in road:
if a == node:
next_dist = cost + distance
if next_dist < distances[b]:
distances[b] = next_dist
que.put((next_dist, b))
elif b == node:
next_dist = cost + distance
if next_dist < distances[a]:
distances[a] = next_dist
que.put((next_dist, a))
return sum(1 for d in distances if d <= K)테스트 1 〉 통과 (0.54ms, 10.9MB)
테스트 2 〉 통과 (0.52ms, 10.8MB)
테스트 3 〉 통과 (0.49ms, 10.8MB)
테스트 4 〉 통과 (0.52ms, 10.8MB)
테스트 5 〉 통과 (0.57ms, 10.8MB)
테스트 6 〉 통과 (0.55ms, 10.8MB)
테스트 7 〉 통과 (0.53ms, 10.8MB)
테스트 8 〉 통과 (0.54ms, 10.8MB)
테스트 9 〉 통과 (0.48ms, 10.8MB)
테스트 10 〉 통과 (0.59ms, 10.8MB)
테스트 11 〉 통과 (0.57ms, 10.8MB)
테스트 12 〉 통과 (0.73ms, 10.8MB)
테스트 13 〉 통과 (0.64ms, 10.8MB)
테스트 14 〉 통과 (2.71ms, 11.1MB)
테스트 15 〉 통과 (4.07ms, 11.6MB)
테스트 16 〉 통과 (0.61ms, 10.8MB)
테스트 17 〉 통과 (0.64ms, 10.8MB)
테스트 18 〉 통과 (1.67ms, 10.9MB)
테스트 19 〉 통과 (4.58ms, 11.2MB)
테스트 20 〉 통과 (1.58ms, 10.9MB)
테스트 21 〉 통과 (5.14ms, 12.3MB)
테스트 22 〉 통과 (2.12ms, 10.8MB)
테스트 23 〉 통과 (5.77ms, 12MB)
테스트 24 〉 통과 (3.94ms, 11.3MB)
테스트 25 〉 통과 (6.73ms, 13.4MB)
테스트 26 〉 통과 (6.75ms, 13.3MB)
테스트 27 〉 통과 (6.81ms, 13.4MB)
테스트 28 〉 통과 (7.47ms, 13.6MB)
테스트 29 〉 통과 (7.01ms, 13.5MB)
테스트 30 〉 통과 (6.55ms, 13.6MB)
테스트 31 〉 통과 (0.83ms, 10.8MB)
테스트 32 〉 통과 (0.96ms, 10.8MB)힙큐와 우선순위큐와의 속도 비교도 한번..
def solution(N, road, K):
from heapq import heappush, heappop
distances = [float('inf') for i in range(N + 1)]
distances[1] = 0
que = []
heappush(que, (0, 1))
while que:
distance, node = heappop(que)
if distance > distances[node]: # 없어도 작동은 하지만.. 속도를 위해..
continue
for a, b, cost in road:
if a == node:
next_dist = cost + distance
if next_dist < distances[b]:
distances[b] = next_dist
heappush(que, (next_dist, b))
elif b == node:
next_dist = cost + distance
if next_dist < distances[a]:
distances[a] = next_dist
heappush(que, (next_dist, a))
return sum(1 for d in distances if d <= K)테스트 1 〉 통과 (0.05ms, 10.8MB)
테스트 2 〉 통과 (0.05ms, 10.8MB)
테스트 3 〉 통과 (0.05ms, 10.7MB)
테스트 4 〉 통과 (0.06ms, 10.9MB)
테스트 5 〉 통과 (0.07ms, 10.8MB)
테스트 6 〉 통과 (0.05ms, 10.7MB)
테스트 7 〉 통과 (0.06ms, 10.8MB)
테스트 8 〉 통과 (0.06ms, 10.8MB)
테스트 9 〉 통과 (0.04ms, 10.9MB)
테스트 10 〉 통과 (0.06ms, 10.8MB)
테스트 11 〉 통과 (0.07ms, 10.8MB)
테스트 12 〉 통과 (0.16ms, 10.8MB)
테스트 13 〉 통과 (0.11ms, 10.8MB)
테스트 14 〉 통과 (1.96ms, 11.1MB)
테스트 15 〉 통과 (2.95ms, 11.6MB)
테스트 16 〉 통과 (0.08ms, 10.9MB)
테스트 17 〉 통과 (0.10ms, 10.8MB)
테스트 18 〉 통과 (0.88ms, 10.7MB)
테스트 19 〉 통과 (3.52ms, 11.2MB)
테스트 20 〉 통과 (0.79ms, 10.8MB)
테스트 21 〉 통과 (4.15ms, 12.3MB)
테스트 22 〉 통과 (1.22ms, 10.9MB)
테스트 23 〉 통과 (4.38ms, 12MB)
테스트 24 〉 통과 (2.91ms, 10.9MB)
테스트 25 〉 통과 (5.63ms, 13.2MB)
테스트 26 〉 통과 (5.96ms, 13.3MB)
테스트 27 〉 통과 (5.41ms, 13.4MB)
테스트 28 〉 통과 (6.24ms, 13.6MB)
테스트 29 〉 통과 (5.91ms, 13.6MB)
테스트 30 〉 통과 (6.18ms, 13.5MB)
테스트 31 〉 통과 (0.20ms, 10.8MB)
테스트 32 〉 통과 (0.34ms, 10.9MB)최댓값이 필요할 때 type이 있는 언어는
type에 따른 최댓값을 이용하는 경우가 많은데,
파이썬은 type이 없어서 애매하다.
이때 math.inf 나 sys.maxsize 등을 이용해도 되겠지만,
외부 모듈을 불러와야 하는 불편함이 있어서
float('inf')를 즐겨 쓴다.
반응형