[이코테/정렬] 카드 정렬하기

병아리는삐약삐약 2023. 10. 18. 15:20

문제

1715번: 카드 정렬하기

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장

www.acmicpc.net

정답

import heapq
n = int(input())
heap = []
for i in range(n):
    data = int(input())
    heapq.heappush(heap,data) 
    # 만들어놓은 heap배열에 data를 넣을건데 기존의 값들과 비교해서 더 작은 값이 앞에 오도록 넣음
    # 데이터의 삽입,수정,갱신에 따라 자동으로 재정렬됨

result = 0

while len(heap) != 1: # heap에 원소가 하나만 남게 되면 그 값은 result와 같을 것이므로 결과를 출력.
    # 가장 작은 값 두개 꺼내기
    one = heapq.heappop(heap)
    two = heapq.heappop(heap)
    # 가장 작은 값 두 개를 결과값에 더하고 다시 heap에 넣기 
    # -> 자동으로 정렬되기 때문에 다음에 또 가장 작은 값 2개를 꺼낼 수 있음음
    sum_value = one+two
    result += sum_value
    heapq.heappush(heap,sum_value)

print(result)

풀이

논리적으로 가장 작은 묶음을 두 개씩 더해나가면 최소횟수의 해를 찾을 수 있다는 건 알았는데

이걸 코드로 어떻게 구현할 지 몰라서 빠르게 답지를 참고했다.

데이터의 값이 작은 걸 높은 우선순위로 자동 정렬해주는 heapq를 사용해서 풀면 되는 문제였다.

이런건 그냥 많이 풀어보면서 익히는게 답인듯..!

참고

이것이 취업을 위한 코딩테스트다.(with.python)