[ BOJ / Python ] 1715번 카드 정렬하기
이번 문제는 우선순위큐를 사용하여 우선순위큐의 크기가 1보다 클 동안 가장 작은 두 수를 더한 값을 결과값에 계속해서 더해주어 해결하였다.
가장 작은 두 카드덱을 합치는 것이 가장 작은 결과를 도출한다는 패턴을 쉽게 알 수 있었다.
초기에는 우선순위큐를 사용하지 않고 리스트를 사용하여 while문 안에서 매 반복마다 .sort()함수를 사용해 오름차순 정렬하였는데 이는 while문의 O(n)과 .sort()함수의 O(n)이 곱해져 시간복잡도가 O(n^2)가 나오기 때문에 당연히 시간초과가 발생하였다.
파이썬에서 우선순위큐는 힙을 사용하여 구현할 수 있다.
- heapq를 참조한다.
- n을 입력받는다.
- 카드 수를 저장할 배열 card를 선언한다.
- n번 반복하는 i에 대한 for문을 돌린다.
-> heapq의 heappush를 사용하여 card에 카드 수를 입력받는다. heappush를 하게 되면 지정된 우선순위로 자동 정렬된다. 지정된 우선순위가 따로 없다면 기본값인 오름차순으로 정렬된다. - 결과값을 저장할 변수 answer를 0으로 정의한다.
- card의 길이가 1보다 클 동안 반복하는 while문을 돌린다. (길이가 1이면 돌지 않고 넘어간다.)
-> 임시 변수 tmp1을 선언하고 heapq의 heappop()을 사용해 card에서 우선순위가 가장 높은 값을 tmp1에 넣어주고 card에서 제거한다.
-> 임시 변수 tmp2를 선언하고 heapq의 heappop()을 사용해 card에서 우선순위가 가장 높은 값을 tmp2에 넣어주고 card에서 제거한다.
-> answer에 tmp1+tmp2의 값을 더한다.
-> heapq의 heappush()를 사용해 tmp1+tmp2를 card의 우선순위에 맞는 자리에 넣어준다. - answer를 출력한다.
Code
import heapq
n=int(input())
card=[]
for i in range(n):
heapq.heappush(card, int(input()))
answer=0
while len(card)>1:
tmp1=heapq.heappop(card)
tmp2=heapq.heappop(card)
answer+=(tmp1+tmp2)
heapq.heappush(card, tmp1+tmp2)
print(answer)
import heapq
n=int(input())
card=[]
for i in range(n):
heapq.heappush(card, int(input()))
answer=0
while len(card)>1:
tmp1=heapq.heappop(card)
tmp2=heapq.heappop(card)
answer+=(tmp1+tmp2)
heapq.heappush(card, tmp1+tmp2)
print(answer)
Author And Source
이 문제에 관하여([ BOJ / Python ] 1715번 카드 정렬하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@xx0hn/BOJ-Python-1715번-카드-정렬하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)