[TIL]25-01-02

https://www.acmicpc.net/problem/1715
요 문제를 풀었다.
주어진 숫자들을 오름차순으로 정렬하고 하나하나 합쳐가는게 빠를거라고 생각은했고,
문제 분류를 보고 힙정렬을 사용해서 nlogn 시간 복잡도로 풀어야 한다는 걸 배웠다.

import heapq
import sys
sys.setrecursionlimit(10**6)
N = int(input())

nums = [int(input()) for _ in range(N)]

heapq.heapify(nums)

result = 0


def card_count(a, arr):
    global result
    if len(arr) == 0:
        return result
    result += a + heapq.heappop(arr)
    return card_count(result, arr)


num = heapq.heappop(nums)
print(card_count(num, nums))

처음 내가 힌트 보고 작성한 코드, 지피티 선생님께 물어보니 시간복잡도는 괜찮은데 재귀때문에 메모리 초과가 난다고 하셨다.

import heapq

N = int(input())

nums = [int(input()) for _ in range(N)]

heapq.heapify(nums)

result = 0

while len(nums) > 1:
    num_1 = heapq.heappop(nums)
    num_2 = heapq.heappop(nums)
    cost = num_1+num_2
    result += cost
    heapq.heappush(nums, cost)


print(result)

재귀를 쓰지 않는 방향으로 고쳤더니 맞았다.

힙 정렬에 쓰임에 대해 한번 더 배우는 시간이였다.

힙에서 최소 두 개의 값을 꺼냄: 𝑂(log⁡𝑁) (힙의 heappop은 O(logN)).
결과를 다시 힙에 삽입:O(logN).

이 두 작업을 N-1 번 반복하기 때문에 총 𝑂(Nlog⁡𝑁)의 시간복잡도로 동작하게 된다.