[Problem Solving] 백준 1715번 카드 정렬하기 문제 풀이

백준 1715번 카드 정렬하기 문제 풀이에 대해서 알아보겠습니다. 문제 해설은 다음의 링크를 확인해주시기 바랍니다.

https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

 

해당 문제는 그리디 유형의 문제로 문제를 해결하기 위한 최적의 방법을 생각해보아야 합니다. 최소 비교 횟수를 구하기 위해서는 가장 작은 묶음을 뽑아서 비교해줘야 합니다. 문제 해결을 위해서는 다음의 과정을 거칩니다.

 

1. 첫 번째로 작은 묶음을 선택한다.
2. 두 번째로 작은 묶음을 선택한다.
3. 두 묶음을 하나로 합친다.
4. 1의 과정을 반복한다.

예를 들어 n = 4, data=[10,20,20,20]의 정보가 있다고 하겠습니다. 이때 첫 번째로 작은 묶음은 A, 두 번째로 작은 묶음은 B라고 하겠습니다. 두 묶음을 합친 것을 C, 결괏값을 answer라고 하겠습니다.

 

첫 번째 반복: A=10, B=20, C=30, answer=30 

두 번째 반복: A=20, B=20, C=40, answer=70

세 번째 반복: A=30, B=40, C=70, answer=140

 

위의 과정을 코드로 구현하면 다음과 같습니다.

 

import heapq

n = int(input())

data = []
answer = 0

for _ in range(n):
  data.append(int(input()))

if n == 1:
  print(0)
else:
  heapq.heapify(data)
  
  while len(data) > 1:
    temp1 = heapq.heappop(data)
    temp2 = heapq.heappop(data)
    heapq.heappush(data, temp1+temp2)
    answer += temp1 + temp2
  print(answer)

 

처음 문제를 해결할 때 리스트를 사용하였는데 리스트를 사용하면 시간 초과가 나와서 heapq를 사용하여 구현하였습니다. heapq를 사용하니 가장 작은 묶음을 선택하는데 리스트만큼의 시간 복잡도가 필요하지 않고, 코드도 더 간결하게 구현할 수 있었습니다.