백준 1715번 카드 정렬하기
https://www.acmicpc.net/problem/1715
문제
풀이
처음에 푼 방식 (시간 초과)
n = int(input())
nlist = []
for _ in range(n):
nlist.append(int(input()))
nlist.sort()
answer = []
while len(nlist) >= 2:
twosum = nlist[0] + nlist[1]
answer.append(twosum)
nlist.append(twosum)
nlist.pop(0)
nlist.pop(0)
nlist.sort()
print(sum(answer))작은 두 수를 더하고 그 수를 nlist 에 넣고. 작은 두 수를 제거하고.
이걸 nlist 의 원소 개수가 2 이하일 때까지 무한반복.
나중에 answer의 합을 구해주면 된다고 생각.
하지만 역시나 시간초과,,,
문제를 찾아보니 heapq 힌트 발견.
heapq는 최소힙으로 동작.
import heapq 만 해주면 되는 간단한 아이.
가장 작은 요소가 항상 첫 번째에 요소에 위치하지만 두 번째 작은 요소는 어디 위치하는 지 모른다.
import heapq
import sys
input = sys.stdin.readline
n = int(input())
nlist = []
for _ in range(n):
nlist.append(int(input()))
heapq.heapify(nlist)
answer = 0
while len(nlist) >= 2:
# 가장 작은 두 요소를 제거하여 합을 구함
first = heapq.heappop(nlist)
second = heapq.heappop(nlist)
twosum = first + second
# 합을 정답에 추가
answer += twosum
# 합을 다시 힙에 추가
heapq.heappush(nlist, twosum)
print(answer)차이점 두 개
1. answer 를 리스트로 만들어서 다 더해주는 방식 대신 반복하면서 계속 더하기 스킬 이용
2. 리스트를 heapify 를 통해 힙으로 변경해줘서 정렬 없이도 작은 두 수를 손쉽게 제거
📌 주의
리스트 안에서 최소 숫자 빠르게 구하기? -> heapq
leenthepotato