[백준] 1715. 카드 정렬하기 Python

문제 링크 : 1715. 카드 정렬하기

1715번: 카드 정렬하기

 

풀이 코드 : GIthub

문제

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

 

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다.

 

예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

 

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

 

풀이

첫 번째 풀이

 

구상

• 먼저 "계속 작은 값끼리 더해가면 최소의 값을 구할 수 있다." 로 접근하였다.

10, 20, 30, 40 4개의 숫자카드 묶음이 있을 때 최소비교 구하는 방법

• 위 그림처럼 제일 작은 숫자가 작은 카드묶음 2개의 묶음을 합친 뒤 계속 그 숫자가 적은 것을 더해 나간다. 
• 더해진 숫자의 결과를 모두 합하면 총 비교 수가 나온다.

 

코드

import sys 
N = int(sys.stdin.readline())
Cards = []
for i in range(N):
    card = int(sys.stdin.readline())
    Cards.append(card)


compare_counts = 0
Cards.sort()
if N == 1:
    compare_counts = 0
elif N == 2:
    compare_counts = Cards[0] + Cards[1]
else:
    for i in range(0, N-1):
        added = Cards[0] + Cards[1]
        Cards.append(added)
        compare_counts += added
        Cards = Cards[2:]
        Cards.sort()

print(compare_counts)

 

• 카드 묶음의 숫자를 list로 저장한다.
• 카드의 묶음들을 숫자순으로 정렬한다.
• 작은 순서대로 묶음을 합치기 시작한다.
• 합칠때마다 합쳐진 숫자를 더한다. 그리고 다시 정렬한다.

 

결과

그러나 시간초과

 

결과는 시간초과였다.

매 카드 묶음을 합할 때마다 작은 수끼리 합하기 위해 list를 정렬한 것에서 시간초과가 발생한 것으로 예상된다.

 

 

두 번째 코드

import sys 
import heapq


N = int(sys.stdin.readline())
Cards = []
for i in range(N):
    card = int(sys.stdin.readline())
    heapq.heappush(Cards, card)


compare_counts = 0

if N == 1:
    compare_counts = 0
elif N == 2:
    compare_counts = Cards[0] + Cards[1]
else:
    for i in range(0, N-1):
        added = heapq.heappop(Cards) + heapq.heappop(Cards)
        heapq.heappush(Cards, added)
        compare_counts += added
    

print(compare_counts)

 

• 전체적인 개념은 첫번째와 동일하지만 카드묶음을 합칠 때마다 정렬하는것을 피하기 위해 heapq를 사용한다.

두 번째 코드 결과

정답이 나왔다.

 

정답이 나왔다. 

파이썬의 sort내장함수의 시간복잡도는 O(n log n) 이라 하더라 (평균, 최악)

그러나 heapq의 시간복잡도는 다음과 같다.

Operation	Time Complexity - Worst Case
Get Item	O(1)
Insert Item	O(logn)
Delete Item	O(logn)
Search Item	O(n)

 

list의 sort보다 훨씬 빠른 시간복잡도를 보인다.

 

그래서 다음과 같은 상황에서 heapq를 사용하면 좋을 것 같다.

 

1. 데이터가 지속적으로 정렬이 되어야 할 때

2. 데이터의 삽입 / 삭제가 빈번히 일어날 때