Minimum Cost of Ropes

Q: Minimum Cost of Ropes의 시간 복잡도는 얼마인가요?

최소 힙을 사용하면 시간 복잡도는 O(n log n) , 공간 복잡도는 O(n) 입니다. n-1 번 합치며, 각 합치기마다 O(log n) 의 힙 연산을 세 번 수행합니다. 대신 가장 짧은 로프 두 개를 찾기 위해 전체 더미를 탐색하면 시간 복잡도는 O(n²) 이 됩니다.

쉬움힙 그리디

+10

몇 개의 밧줄이 있고, ropes[i]는 밧줄 i의 길이입니다. 임의의 밧줄 두 개를 하나로 합칠 수 있으며, 합쳐진 밧줄의 길이는 두 밧줄 길이의 합이고, 합치는 비용도 같은 합입니다. 밧줄 하나만 남을 때까지 계속 합칩니다.

모든 밧줄을 하나로 합치는 최소 총비용을 반환하는 minCostRopes라는 함수를 작성하세요. 처음부터 밧줄이 하나뿐인 경우에는 0을 반환합니다.

함수

minCostRopes(ropes: integer-array) → integer

ropesinteger-array: 각 밧줄의 길이
반환값integer: 모든 로프를 하나로 합치는 최소 총비용

제약 조건

1 ≤ ropes.length ≤ 10⁴
1 ≤ ropes[i] ≤ 100
답은 32비트 부호 있는 정수 범위에 들어갑니다.

예제

입력: ropes = [5, 2, 8, 3]
출력: 33
설명: 2와 3을 합쳐 5를 만들고, 길이가 5인 두 로프를 합쳐 10을 만든 다음, 8과 10을 합쳐 18을 만듭니다. 합계는 5 + 10 + 18 = 33입니다.

입력: ropes = [1, 1, 1, 1]
출력: 8
설명: 1들을 쌍으로 묶어 각각 2의 비용이 들고, 그다음 길이가 2인 두 로프를 합치면 4의 비용이 듭니다. 총 8입니다. 각 1을 계속 길어지는 로프 하나에 더하면 비용은 2 + 3 + 4 = 9가 됩니다.

후속 질문

한 번의 연결로 최대 세 개의 밧줄을 묶을 수 있고 비용은 밧줄 길이의 합이라고 가정해 보세요. 밧줄의 개수가 균등하게 나누어떨어지지 않을 때 탐욕적 규칙은 어떻게 달라질까요?

풀이

매번 연결할 때 두 조각의 전체 길이에 해당하는 비용을 지불하므로, 일찍 연결된 로프는 이후에 포함되는 모든 연결에서 다시 비용이 듭니다. 긴 로프는 초반 연결에서 제외하세요. 매 라운드마다 가장 짧은 로프 두 개를 연결하세요. 최소 힙을 사용하면 O(log n)에 이 두 개를 찾을 수 있습니다.

매 라운드마다 가장 짧은 두 개를 찾으세요

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

각 라운드마다 더미를 훑어 가장 짧은 밧줄을 꺼내고, 다시 훑어 다음으로 짧은 밧줄을 꺼낸 다음 두 밧줄을 이어 만든 밧줄을 다시 넣습니다.

왜 가장 짧은 두 밧줄일까요? 밧줄을 잎으로 하는 트리로 이어 붙이는 과정을 그려 보세요. 밧줄의 길이는 그 밧줄 위에 있는 모든 연결마다 한 번씩 비용으로 계산되며, 그 횟수가 바로 밧줄의 깊이입니다. 가장 깊은 레벨에는 나란히 있는 잎 두 개가 있고, 가장 짧은 두 밧줄을 그곳으로 옮겨도 비용은 늘어나지 않습니다. 따라서 가장 저렴한 방법 중 하나는 가장 짧은 두 밧줄을 먼저 연결하는 것이며, 더미가 작아진 뒤에도 같은 논리가 반복됩니다.

두 번의 전체 탐색을 n-1라운드 수행합니다. 시간 복잡도는 O(n²)이며, 밧줄이 10^4개일 때 비교 횟수는 약 10^8회입니다.

알고리즘

밧줄들을 작업 목록인 pile에 복사하고, total을 0으로 시작합니다.
밧줄이 하나 남을 때까지 반복합니다. 가장 짧은 밧줄을 찾아 마지막 밧줄을 그 자리에 옮겨 제거합니다.
같은 작업을 다시 수행해 그다음으로 짧은 밧줄을 찾습니다.
두 밧줄의 길이 합을 total에 더하고, 그 길이의 밧줄을 목록에 추가합니다.
total을 반환합니다.

def minCostRopes(ropes):
    pile = list(ropes)

    def take_shortest():
        k = 0
        for i in range(1, len(pile)):
            if pile[i] < pile[k]:
                k = i
        pile[k], pile[-1] = pile[-1], pile[k]  # move it to the end, then remove it
        return pile.pop()

    total = 0
    while len(pile) > 1:
        joined = take_shortest() + take_shortest()
        total += joined
        pile.append(joined)
    return total

최소 힙

핵심 아이디어

최소 힙은 가장 짧은 로프를 루트에 유지하며, 루트를 꺼내거나 로프를 삽입하는 데 O(log n)의 비용이 듭니다. 한 라운드는 두 번 추출하여 가장 짧은 로프 두 개를 가져오고, 이어 붙인 로프를 한 번 삽입하는 과정입니다.

n개의 로프를 이어 붙이려면 각각 힙 연산 세 번으로 이루어진 n-1번의 이어 붙이기가 필요하므로, 시간 복잡도는 O(n log n)입니다. 10^4개의 로프라면 약 4 × 10^5번의 연산이 필요합니다. 힙에 담기는 로프의 수는 n개를 넘지 않습니다.

알고리즘

모든 로프의 길이를 최소 힙에 넣고 total = 0으로 설정합니다.
로프가 하나 남을 때까지 반복합니다. 가장 짧은 두 개를 꺼냅니다.
두 길이의 합을 total에 더하고, 그 합을 힙에 다시 넣습니다.
total을 반환합니다. 로프가 하나뿐이었던 경우 0으로 유지됩니다.

import heapq


def minCostRopes(ropes):
    heap = list(ropes)
    heapq.heapify(heap)  # a min-heap: heap[0] is the shortest rope
    total = 0
    while len(heap) > 1:
        joined = heapq.heappop(heap) + heapq.heappop(heap)
        total += joined
        heapq.heappush(heap, joined)
    return total

함정과 경계 사례

한 번 정렬한 뒤 각 로프를 누적 로프에 더하는 것. 누적 로프는 아직 사용하지 않은 로프보다 길어질 수 있습니다. [2, 3, 4, 4]의 경우 비용은 5 + 9 + 13 = 27이지만, 가장 짧은 두 로프를 연결하면 5 + 8 + 13 = 26입니다.
연결한 로프를 제외하는 것. 로프의 길이는 다시 더미에 들어가며, 나중에 연결할 때 다시 비용으로 계산됩니다.
마지막 로프의 길이를 반환하는 것. [5, 2, 8, 3]의 경우 마지막 로프의 길이는 18이지만, 비용은 33입니다.
실수로 최대 힙을 사용하는 것. C++ priority_queue와 Rust의 BinaryHeap은 순서를 뒤집지 않으면 가장 큰 값을 꺼냅니다.

자주 묻는 질문3

Minimum Cost of Ropes의 시간 복잡도는 얼마인가요?

최소 힙을 사용하면 시간 복잡도는 O(n log n), 공간 복잡도는 O(n)입니다. n-1번 합치며, 각 합치기마다 O(log n)의 힙 연산을 세 번 수행합니다. 대신 가장 짧은 로프 두 개를 찾기 위해 전체 더미를 탐색하면 시간 복잡도는 O(n²)이 됩니다.

최소 비용 로프 문제는 허프만 코딩과 같은가요?

네, 같은 알고리즘입니다. 허프만 코딩은 빈도가 가장 낮은 두 기호를 반복해서 병합하여 접두사 코드를 만들고, 각 빈도에 트리에서의 깊이를 곱한 값의 합을 최소화합니다. 여기서는 로프가 기호의 역할을 하고 로프의 길이가 빈도의 역할을 하므로, 총비용은 동일한 합입니다.

밧줄의 최소 비용 문제를 힙 없이 해결할 수 있을까요?

네, 큐 두 개를 사용하면 됩니다. 로프를 정렬해 한 큐에 넣고, 이어 붙인 각 로프는 두 번째 큐의 뒤에 넣습니다. 이어 붙인 로프는 감소하지 않는 순서로 나오므로, 남은 로프 중 가장 짧은 로프는 한 큐의 앞에 있습니다. 그러면 각 라운드는 O(1)이고, 길이가 최대 100이므로 계수 정렬을 사용하면 실행 시간이 O(n)입니다.

def minCostRopes(ropes):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자

ropes = [5, 2, 8, 3]

예상 출력