[파이썬] 백준 알고리즘 No.1715 카드 정렬하기

백준 1715번 카드 정렬하기 문제

 

 

n = int(input())
data = []
for _ in range(n):
    data.append(int(input()))
data.sort()

if len(data) == 1:
    print(data[0])
    exit()

result = 0
result += data[0] * (len(data) - 1)
for i in range(1, len(data)):
    result += data[i] * (len(data) - i)
print(result)

최초 코드

 

import heapq
n = int(input())
data = list(int(input()) for _ in range(n))
heapq.heapify(data) # heapify를 통해 기존 리스트를 heap으로 변환
result = 0

while len(data) != 1:
    num1 = heapq.heappop(data)
    num2 = heapq.heappop(data)
    result += num1 + num2
    heapq.heappush(data, num1 + num2)
print(result)

최종 코드

 

최종 코드 제출

 

 

최초에는 데이터 값들의 연속성을 발견하여

 

n

n - 1 / n - 1

n - 1 / n - 1 / n - 2

n - 1 / n - 1 / n - 2 / n -3

n - 1 / n - 1 / n - 2 / n - 3 / n - 4 

.....................

 

을 기본항으로 문제를 풀어보려 했으나

 

우리가 구해야하는건 최소의 값

즉 데이터를 정렬해서 제일 작은 두 항을 묶고, 그 항을 다시 리스트의 맨 앞으로 불러들여

또 다시 제일 작은 두 항을 묶어야 하는 문제였다 ( 1개가 남을 때 까지 )

 

원래는 heap을 사용하지 않고, list를 사용하여 풀려 했었다

pop(0)를 사용하여 x = pop(0), y = pop(0), data.append(x+y)

하지만 여러가지 한계에 봉착하게 되었다.

 

내일은 heap과 우선순위 큐에 대해서 다시 한번 공부하는 시간을 가져야겠다.