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

🥇 Gold4

https://www.acmicpc.net/problem/13975

 

 

❎ 1차풀이

import sys
from collections import deque
input = sys.stdin.readline

n=int(input())
for _ in range(n):
    m=int(input())
    nums=sorted(list(map(int,input().strip().split())))
    queue=deque(nums)


    result=0
    while len(queue)>=1:
        if len(queue)==1:
            print(result)
            break
             
        temp=queue[0]+queue[1]
        queue.append(temp)
        result+=temp
        if queue:
            queue.popleft() #0
            queue.popleft() #1

        #sort
        queue=deque(sorted(list(queue)))

처음 풀어보는 골드문제에 겁을 먹었지만, 생각보다 굉장히 간단한 방식으로 파일을 합친다. 두개씩 최소의 비용으로 합쳐서 완성시키기 위해선 가장 작은 파일들끼리 묶어나가면 된다. 

 

sort를 해준 상태에서 가장 작은 두개의 파일을 합쳐서(0,1번째) 하나의 파일을 생성해준뒤 또 병합되어어야하기 때문에, 큐에 넣어준다. 새로 생성된 값이 들어오고 반복해서 이 작업을 수행해야 하기 때문에, 또 한번 정렬을 해주어야한다.

 

✨ 맨앞의 요소를 꺼내야하기 때문에 리스트가 아닌 FIFO 큐를 사용하였다. 최종적으로 파일 1개를 완성했을때 결과를 출력해주면된다.

 

sort 작업을 반복해서 수행하기 때문에, 시간초과를 좀 우려하긴했는데 , 역시나 시간초과가 발생하였다..

 

 

• 초기 정렬: O(m log m)
• 반복 루프: 루프는 최대 m-1 번 반복되며, 각 반복마다 정렬을 수행합니다. 각 정렬의 시간 복잡도는 O(m log m)
• 총 시간 복잡도: O((m-1) * m log m) = O(m^2 log m)

 

 

 

 

✅ 정답풀이

import sys
import heapq

input = sys.stdin.readline

n = int(input())
for _ in range(n):
    m = int(input())
    nums = list(map(int, input().strip().split()))
    heapq.heapify(nums)  

    result = 0
    while len(nums) > 1:
        # 두 개의 min값 꺼내기
        first = heapq.heappop(nums)
        second = heapq.heappop(nums)

        # 결과에 추가
        temp = first + second
        result += temp

        # sum값 다시 heap에 넣어주기
        heapq.heappush(nums, temp)

    print(result)

1,2번째 최소값을 추출하는 문제다보니 최소힙으로 변경해보았다.

코드는 굉장히 간결하다. pop으로 꺼낸 값들을 더해주고 새로 생성된값을 push해주는 작업을 반복하면 된다.

 

 

 

• 초기 힙 변환: O(m)
• 반복 루프: O(m log m)
• 전체 시간 복잡도: O(m log m)