[알고리즘] 카드 정렬하기 - 백준 1715

1.문제

카드 정렬하기

2. 접근

1. 처음에 받는 데이터들을 heap에 넣어서 차순 정렬을 한다

2. 받은 데이터들의 더해진 값들에 대한 리스트를 만들어준다.

3. 2번째 만든 데이터들의 합을 구하여 출력한다

 

< 내 생각 >

처음부터 같은 생각을 가지고 문제를 풀었다.

솔직히 처음 문제 풀이에 대해서 아직 뭐가 틀린지 잘 모르겠다.

 

하여튼, 주어진 수들의 합을 새로운 공간에 넣고 새로운 리스트의 원소들의 합을 구한다는 생각으로 풀었다

 

3. 풀이

처음에 틀린 풀이

# 카드 정렬하기
import sys
input = sys.stdin.readline

n = int(input())

data = []
for i in range(n):
    data.append(int(input()))
res = []

data.sort()

res.append(data[0]+data[1])

for i in range(2, n):
    res.append(res[i-2]+data[i])

print(sum(res))

 

맞은 풀이

# 카드 정렬하기
import sys
import heapq
input = sys.stdin.readline

n = int(input())
res = []

heap = []
for i in range(n):
    data = int(input())
    heapq.heappush(heap, data)

while len(heap) != 1:
    one = heapq.heappop(heap)
    two = heapq.heappop(heap)
    sumValue = one + two
    res.append(sumValue)
    heapq.heappush(heap, sumValue)

print(sum(res))