BOJ_1715_카드 정렬하기_python_[그리디]

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

1715번: 카드 정렬하기

1) 문제

2) 예시

3) 제출

import sys
import heapq
input = sys.stdin.readline

n = int(input())
answer = 0
card = []
for i in range(0, n):
    heapq.heappush(card, int(input()))

while len(card) > 1:
    tmp = heapq.heappop(card)
    tmp += heapq.heappop(card)
    answer += tmp
    heapq.heappush(card, tmp)

print(answer)

4) 메모리/시간/코드 길이

5) PLUS

어떻게 해야할지 모르겠어서 우선 시간복잡도는 생각하지 않고, 코드로만 구현을 해봤다.

처음 구현했을 때는 

1. 리스트에 입력받기

2. while문 돌리기

    가장 작은 두 값을 pop한 후, 더하기

    두 합을 다시 list에 append하기

    list 정렬

의 반복이었다.

 

하지만 정렬의 시간복잡도는 nlogn이다. 

 

그래서 구글링을 해봤고 heap을 써봤다. 

heap은 push함과 동시에 정렬되어 들어감으로 시간이 훨씬 들어간다.