[정렬] 카드 정렬하기

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 30분 + a

1. 문제 설명

- 여러 카드 뭉치가 있을 때, 하나의 뭉치로 카드를 정렬할 때 최소한의 횟수로 정렬하는 방법을 묻는 문제

2. 접근 방식

- 처음에는 단순하게 생각해서 reduce를 활용해서 문제를 풀 수 있지 않을까 했었는데 조금 더 복잡했던 문제였다.

- 그래프처럼 생각해서 문제를 풀었어야 했다. heapq 라이브러리를 활용해서 문제를 풀었어야 했다. (heap은 자동적으로 최소값을 빼준다_heapq를 활용할 때 최대힙을 활용하는 트릭도 같이 기억하면 좋아보인다.)

3. 코드

import heapq
n = int(input())
heap = []
result = 0

for _ in range(n):
    heapq.heappush(heap, int(input()))
while len(heap)!=1:
    a = heapq.heappop(heap)
    b = heapq.heappop(heap)
    result += a+b
    heapq.heappush(heap, a+b)
print(result)

4. 코멘트

- 문제의 주제가 정렬이지, 정렬을 하는 문제는 아니었던 걸로...
- heap을 활용해서 최소값끼리 더해주고 이를 다시 넣어 최소값끼리 더해주고...
- 문제를 풀다가 수가 여러 개 들어왔을 때 최소값의 기준이 달라질 경우 순차탐색으로 어떻게 할까에 대해 생각이 들었었다. 결국 이러한 문제점을 해결할 수 있는 방법이 'heapq'였다.