카드 정렬하기 ( 1715 번 )

1715번: 카드 정렬하기

 

---

🧠 알고리즘

• 최소 힙(Min Heap)을 이용한 Greedy(탐욕) + 우선순위 큐 기반 누적 최소 비용 계산

 

✔️ 동작 방식

• 핵심 아이디어
  항상 가장 작은 두 값부터 합쳐야 전체 비용 최소.
• 로직 요약
  1. 모든 숫자를 최소 힙에 넣는다.
  2. 힙에서 가장 작은 두 값을 꺼낸다.
  3. 두 값을 더한 비용을 정답에 누적한다.
  4. 합친 값을 다시 힙에 넣는다.
  5. 힙에 값이 한 개 남을 때까지 반복한다.

---

 

🧾 코드

import sys, heapq

def _main():
    answer = 0
    hq = []
    
    for _ in range(n):
        number = int(sys.stdin.readline().rstrip())
        heapq.heappush(hq, number)

    while len(hq) != 1:
        num1 = heapq.heappop(hq)
        num2 = heapq.heappop(hq)
        answer += (num1 + num2)

        heapq.heappush(hq, num1 + num2)

    return answer

n = int(sys.stdin.readline().rstrip())
print(_main())

---

 

⏱️ 시간 복잡도

while len(hq) != 1 : 조건 만족시 까지 힙 연산 ( 선형 로그 )
    heapq.heappop(hq)
    
해당 알고리즘 시간 복잡도 : 선형 로그 시간 복잡도 ( O(n log n) )