백준 1715.카드 정렬하기 (Python)

문제

시간초과 문제가 있었던 답안

N = int(input())
card_list = list(int(input()) for _ in range(N))
card_list.sort()

answer = 0 # 답
sum = 0 # 단계마다의 합
while(True):
  sum = card_list[0]+card_list[1]
  card_list.pop(0)
  card_list[0] = sum
  card_list.sort()
  answer += sum
  if len(card_list) == 0:
    break
  elif len(card_list) == 1:
    break

print(answer)

 

시간초과 문제가 일어났던 이유는? 선형리스트를 사용했기 때문에...!!

선형리스트를 사용하면 안되는 이유는 요기 블로그에 !! 👉🏻  https://joni-dev.tistory.com/2

 

그러면 우리가 시간초과를 해결하기 위해서는? 우선순위 큐를 사용해야 한다!!

우선순위 큐란?

일반적으로 먼저 들어온 데이터가 먼저 처리되는 일반적인 큐와 달리, 우선순위가 높은 데이터부터 처리되는 자료구조

그런데 파이썬에서 우선순위 큐를 구현하는 방법에 대표적인 2가지가 있다

   1. PriorityQueue

   2. Heap

1. PriorityQueue

from queue import PriorityQueue

pq = PriorityQueue()

pq.put(1)  # pq.put((1, "조은"))
pq.put(3)  # pq.put((3, "우선순위큐"))
pq.put(2)  # pq.put((2, "힙"))

pq.get() # 1
pq.get() # 2
pq.get() # 3

 

2. Heap

pq = []

heapq.heappush(pq, 1)
heapq.heappush(pq, 3)
heapq.heappush(pq, 2)

heapq.heappop(pq) # 1
heapq.heappop(pq) # 2
heapq.heappop(pq) # 3

 

연결리스트로 삽입 또는 삭제 연산을 진행하면 시간복잡도는 ➡️ O(n)

힙은 완전이진트리 구조이므로 힙트리의 높이는 log2(n+1)이며, 시간복잡도는 ➡️ O(log2n)이다.

 

근데? 사실 heapq가 PriorityQueue보다 실행시간이 적게 걸려 heapq를 일반적으로 사용하지만?

저는 그냥 우선순위 큐 써보고 싶어서 우선순위 큐로 풀었어요!

또, PriorityQueue와 heapq는 최소 힙만 다룰 수 있기 때문에 큰 수부터 pop하고 싶다면 -부호를 붙혀 push하면 된다.

✅ 정답

import sys
from queue import PriorityQueue

N = int(sys.stdin.readline())
priority_queue = PriorityQueue()
for _ in range (N):
  card = int(sys.stdin.readline())
  priority_queue.put(card)

answer = 0 # 답
sum = 0 # 단계마다의 합

if N != 1:
  while(True):
    min1 = priority_queue.get()
    min2 = priority_queue.get()
    sum = min1+min2
    priority_queue.put(sum)
    answer += sum
    if priority_queue.qsize() == 0:
      break
    elif priority_queue.qsize() == 1:
      break

print(answer)

 

그런데.. 우선순위 큐로 바꿔서 구현을 해도 91%에서 갑자기 오래 걸리더니 시간초과..

질문 게시판에서 반례를 찾아보니 카드가 한 묶음이면 0이 나와야 한다... 멍청쓰... 😳

 

아무튼!! 오늘 알고리즘 블로그는 여기서 끝!!