파이썬 알고리즘 219번 | [백준 1715번] 카드 정렬하기 - 그리디

219. 카드 정렬하기

1) 어떤 전략(알고리즘)으로 해결?

• 그리디

2) 코딩 설명

• 리스트 원소가 하나 초과인 경우, 리스트에서 항상 가장 작은 두개를 더하고 , 그 두개를 리스트에서 제거해주고 더한 값 하나를 리스트에 넣어주는 것 반복

<내 풀이>

import heapq
import sys

n = int(sys.stdin.readline().strip())
candlis = []
for i in range(n) :
    heapq.heappush(candlis,int(sys.stdin.readline().strip()))
res = 0

while len(candlis)>1 :
        now=(heapq.heappop(candlis)+heapq.heappop(candlis))
        res+=now
        heapq.heappush(candlis,now)

print(res)

2023-02-09 재풀이

import sys
import heapq

n = int(sys.stdin.readline().rstrip())
card = []
for i in range(n) :
    heapq.heappush(card, int(sys.stdin.readline().rstrip()))
answer = 0
while card : 
    a = heapq.heappop(card)
    if card : 
        b = heapq.heappop(card)
        if len(card)==0 :
            if n%2==0 :
                answer+=(a+b)
                break
        answer+=(a+b)
        heapq.heappush(card, (a+b))
print(answer)

<내 틀렸던 풀이, 문제점>

8% 에서 틀린

from collections import deque
import sys

n = int(sys.stdin.readline().strip())
nlis = []
for i in range(n) :
    nlis.append(int(sys.stdin.readline().strip()))
nlis.sort()
nlis=deque(nlis)
res = 0
while len(nlis)>1 : 
    now=nlis[0]+nlis[1]
    res+=now
    nlis.popleft(); nlis.popleft()
    nlis.appendleft(now)

print(res)

<반성 점>

• HEAP 사용법 까묵었었다 ㅇㅁㅇ
• 그냥 리스트 선언하고 HEAPPUSH HEAPPOP 만 하면 되는 것

heapq.heappush(candlis,int(sys.stdin.readline().strip()))
res = 0

<배운 점>