[코테] 백준 1715번 카드 정렬하기

문제 링크

문제

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

출력

첫째 줄에 최소 비교 횟수를 출력한다.

풀이

Pseudo Code란?

프로그램을 작성할 때 각 모듈이 작동하는 논리를 표현하기 위한 언어이다. 특정 프로그래밍 언어의 문법에 따라 쓰인 것이 아니라, 일반적인 언어로 코드를 흉내 내어 알고리즘을 써놓은 코드를 말한다.

슈도 코드 작성

N <- input
pq <- 우선순위큐
for N만큼 :
우선순위 큐에 저장
자동 정렬에 따라 작은 카드 묶음 2개를 뽑기
while pq의 갯수가 1이 될까지:
pq에서 2개 추출
2개의 합을 pq에 입력으로 넣기

우선순위 큐란?

PriorityQueue 클래스는 queue 내장 모듈에서 제공되기 때문에 파이썬만 설치되어 있으면 별다른 추가 설치없이 임포트할 수 있다.

from queue import PriorityQueue

PriorityQueue 클래스의 put() 메서드를 이용하여 우선순위 큐에 원소를 추가할 수 있다.

que = PriorityQueue()
que.put(3)
que.put(1)
que.put(1)
que.put(4)
que.put(5)

PriorityQueue 클래스의 get() 메서드를 이용하여 우선순위 큐에 원소를 삭제할 수 있다.

print(que.get())  # 1
print(que.get())  # 1
print(que.get())  # 3
print(que.get())  # 4

코드로 구현해보기

from queue import PriorityQueue      # 우선순위 큐 불러오기
N = int(input())                     # 입력값 받기
pq = PriorityQueue()                         

for _ in range(N):   
    pq.put(int(input()))            # n개 만큼 우선순위 큐에 저장

data1 = 0; data2 = 0; sum = 0      # 우선순위큐에 첫 변수는 data1, 두 번째 변수는 data2에 저장, 카드 묶음의 합 sum에 저장
while pq.qsize() > 1:              # 우선순위 큐에 1개 이상이면
    data1 = pq.get()               # 자동 정렬에 따라 작은 카드 묶음 2개 뽑기
    data2 = pq.get()
    tmp = data1 + data2            # 카드 묶음의 합을 더한 후 tmp에 저장
    sum += tmp                     # tmp는 sum의 저장 후 우선순위 큐에 다시 입력값으로 넣기
    pq.put(tmp)

print (sum)