Programmers LV 2 - in Berlin 6

문제 풀이

두 큐 합 같게 만들기

def solution(queue1, queue2):
    answer = 0
    sum_q1 = sum(queue1)
    sum_q2 = sum(queue2)
    total = (sum_q1 + sum_q2) // 2
    i, j, k = 0, 0, len(queue1)
    while i < 2*k and j < 2*k and sum_q1 != sum_q2:
        if sum_q1 < total:
            sum_q1 += queue2[j]
            sum_q2 -= queue2[j]
            queue1.append(queue2[j])
            j += 1
        else:
            sum_q2 += queue1[i]
            sum_q1 -= queue1[i]
            queue2.append(queue1[i])
            i += 1
    if sum_q1 == sum_q2:
        return i + j
    else:
        return -1

< 풀이 과정 >

• queue1과 queue2의 summation을 각각 변수로 두고, i는 queue1의 인덱스, j는 queue2의 인덱스, k는 두 queue 중 한 개의 길이 (문제에서 두 queue의 길이는 동일하다고 주어졌기에)로 변수를 설정한다.
• 이후 while문으로, queue1의 길이가 두 큐의 길이의 합보다 작아야 하고, queue2 역시 마찬가지이고, 각 queue의 합이 동일하지 않는 경우에만 조건을 실행시킨다.
• sum_q1이 total 보다 작다면 queue2에서 숫자를 가져와 비교를 진행하고, 반대의 경우라면 queue1에서 숫자를 가져와 비교를 진행한다.
• while문을 돌고 sum_q1과 sum_q2가 같다면, i와 j의 합으로 결과를 리턴하고, 아닌 경우 -1을 리턴해준다.

배달

import heapq
def solution(N, road, K):
    inf = 1e9
    graph = [[] for _ in range(N+1)]
    dist = [inf] * (N+1)
    for direction in road:
        a, b, c = direction
        graph[a].append((b, c))
        graph[b].append((a, c))
    
    def dijkstra(start):
        heap = []
        dist[start] = 0
        heapq.heappush(heap, (0, start))
        while heap:
            cost, node = heapq.heappop(heap)
            if dist[node] < cost:
                continue
            for start_node in graph[node]:
                node_plus = cost + start_node[1]
                if node_plus < dist[start_node[0]]:
                    dist[start_node[0]] = node_plus
                    heapq.heappush(heap, (node_plus, start_node[0]))
    dijkstra(1)
    return len([i for i in dist if i <= K])

< 풀이 과정 >
다익스트라 - 최단 경로 탐색 알고리즘을 이용한 문제 풀이.
dist는 모두 무한대로 그려 놓은 후 경로마다 값을 입력하여 최단 경로 찾는 방법 선택

• dist를 무한대로 표기하기 위해 inf = 1e9로 지정하였고, 빈 그래프를 마을 수 (노드 수) 만큼 생성하였다.
• 주어진 road 입력에서 양 방향 이동 정보를 graph에 저장하였다
• 다익스트라 함수를 생성하여 heapq를 이용하여 다음 경로 이동을 선택하였다.
• 빈 힙을 생성하고, 시작 지점을 1로 맞춰준 후 while문을 돈다.
  -- < while문 설명 >
  heappop으로 현재 힙에 저장된 정보를 빼온 후 dist[node] < cost란 방문한 곳이거나, 최솟값보다 작은 경우는 continue로 빠져 나가고, graph 내 주어진 모든 노드들을 순회하여 현재 노드 값의 비용(시간) + 다음 노드 이동 시 추가되는 비용(시간)을 node_plus로 저장한 후 node_plus보다 무한대로 생성해놓은 dist가 더 크면 최단 경로를 발견한 것이므로 업데이트 해주고 heappush로 해당 비용(시간)과 노드를 힙에 저장한다.
• 최종적으로 1번마을로 시작하는 최단경로를 찾는 문제이므로 dijkstra(1)을 실행하면 1번 마을로부터 시작해 각 지점 별 도착 시 최단 경로가 나올 것이고 이때 개수가 K보다 작은 마을 수를 len으로 체크하여 결과를 리턴한다.