[백준/Python] 13975번(그리디, 우선순위 큐)_ 파일 합치기3

📌문제 유형

그리디, 우선순위 큐 (골드 Lv.4)

 

📌문제

13975번: 파일 합치기 3

 

📌나의 문제풀이

- 우선순위 큐 적용한 것(정답)

import heapq

t = int(input())

for _ in range(t):
    ans = 0
    k = int(input())
    chap_nums = list(map(int,input().split()))
    heapq.heapify(chap_nums)

    while True:
        num1 = heapq.heappop(chap_nums)
        num2 = heapq.heappop(chap_nums)
        ans += (num1 + num2)
        heapq.heappush(chap_nums, num1 + num2)

        if len(chap_nums) == 1:
            break

    print(ans)

- 우선순위 큐 적용X (오답)

t = int(input())


for _ in range(t):
    ans = 0
    k = int(input())
    chap_nums = list(map(int,input().split()))

    while True:
        chap_nums.sort()
        num1 = chap_nums.pop(0)
        num2 = chap_nums.pop(0)
        ans += (num1 + num2)
        chap_nums.append(num1 + num2)

        if len(chap_nums) == 1:
            break

    print(ans)

 

📌 다른사람의 문제풀이

- 동일

[Python] 백준 13975 파일 합치기 3

import sys
import heapq

for _ in range(int(sys.stdin.readline())):
    k = int(sys.stdin.readline())
    arr = list(map(int, sys.stdin.readline().split()))
    heapq.heapify(arr)   # 최소힙
    result = 0
    # 가장 작은 2개의 파일 크기를 꺼내서 합친값을 다시 우선순위 큐에 넣기 
    while len(arr) >= 2:
        f = heapq.heappop(arr)
        s = heapq.heappop(arr)
        result += (f + s)
        heapq.heappush(arr, (f + s))
    print(result)

 

📌 리뷰

-입력 개수 꼭 확인하기! (장의 수 k가 1,000,000까지여서 시간 많이 소요되는걸 파악할 수 있음)

- 매번 정렬 + 작은 숫자가 나와야함 + 입력개수 큼 -> 우선순위 큐 적용하기 

- 우선순위 큐 정리 내용

[Python] Heap과 heapq 모듈