난 외로울 때 힙합을 해.. (#1715)

 

#1715 카드 정렬하기 https://www.acmicpc.net/problem/1715

 

다음과 같이 사고했다.

테스트 케이스의 모든 경우의 수를 작성해본 결과, 작은 수의 카드 집합끼리 합치는게 최소값을 도출하는 방법이란걸 알 수 있었다.

 

 

음 좀 어려웠다. 처음 사고대로 구현했는데 시간초과가 났다.

 

틀린코드

from collections import deque

n = int(input())
nums = [int(input()) for _ in range(n)]
nums.sort()
nums = deque(nums)

answer = 0

while len(nums) >= 2:
    # print(answer, nums)
    tmp = nums.popleft() + nums.popleft()
    answer += tmp

    # insert nums
    for i in range(len(nums)):
        if nums[i] > tmp:
            nums.insert(i, tmp)

print(answer)

 

 

아무래도, 첫 sort부분에서 O(n)을 쓰고, insert부분에서 O(n) 혹은 그 이상을 쓴다.

 

 

문제 힌트를 통해서 "우선순위 큐"가 필요함을 알았다.

 

이 문제에서는 우선순위가 수의 크기였던 만큼, 별도의 구현은 필요하지 않았다. 

 

 

정답코드

import heapq

n = int(input())
nums = [int(input()) for _ in range(n)]
# nums.sort()
heapq.heapify(nums)
answer = 0

while len(nums) >= 2:
    # print(answer, nums)
    tmp = heapq.heappop(nums) + heapq.heappop(nums)
    answer += tmp

    # insert nums
    heapq.heappush(nums, tmp)

print(answer)

아주 심플하게 해결되는 골드문제라고 할 수 있다.