26_카드 정렬하기

1715번: 카드 정렬하기

 

카드 비교 횟수가 최소가 되는 총 비교횟수를 출력하면 되는 문제다.

처음에 문제를 읽고, 이게 골드4문제라고? 라는 생각이 들었다.

그래서 5분만에 구현하고 제출하니 바로 시간 초과가 떴다.

문제를 자세히 읽어보니 입력 크기가 최대 100,000개 이므로 단순 비교로는 O(N^2)이라서 당연히 시간 초과가 뜬다.

 

그래서 계속 고민을 해봤다.

고민하다 보니, 이런 규칙이 나왔다.

매번 합칠 카드 묶음을 정할 때, 카드 묶음 리스트 중 가장 작은 값 2개를 골라서 합하면 된다.

그래서 이 방식대로 구현하려고 하다보니, 그러면 매번 가장 작은 값 2개를 뽑아줘야 하는데,

그러면 O(N) * O(NlogN) 시간 복잡도가 나와서 또다시 시간초과가 나온다.

 

그래서 계속계속 고민을 해봤다.

결국 이 문제의 실마리는, 매 시도마다 가장 작은 값 2개를 정렬하지 않고 꺼내는 방법에 있었다.

 

순간 힙이 뇌리에 스쳤다.

힙은 pop할 때마다 가장 우선순위가 높은 값을 먼저 pop해준다.

파이썬 기본 내장 heaq 자료구조는 최소 힙으로 구현되어 있으므로, 카드묶음의 값을 힙에 넣어준 후, 가장 작은 값 2개를 꺼낸 후, 총 합에 더하고, 가장 작은 값 2개의 합을 다시 힙에 넣어주는 방식으로 구현하면 된다.

힙은 자료를 넣고, 빼는데 모두 O(logN) 시간이 소요되므로 시간복잡도도 만족한다.

 

---

내 풀이 코드

# 1715번: 카드 정렬하기
import sys
import heapq # 힙 사용(최소힙)
input = sys.stdin.readline

n = int(input())
card = []

for _ in range(n):
    heapq.heappush(card, int(input()))

total = 0
for i in range(n-1):
    # 가장 작은 값 2개를 빼준다.
    fir = heapq.heappop(card)
    sec = heapq.heappop(card)

    temp = fir + sec
    total += temp
    
    # 2개의 합을 다시 힙에 넣어준다.
    heapq.heappush(card, temp)

print(total)