카드 정렬하기(p.363) - 정렬 문제(이코테)

---

해설 부분은 책에 내용을 포함하고, 더 추가하여 최대한 자세하게 설명하려고 노력했습니다.

---

 

문제 설명

 

정렬된 두 묶음의 숫자 카드가 있을 때 각 묶음의 카드의 수를 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개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작 성학세요. 

 

입력 조건

 

• 첫째 줄에 N이 주어집니다. (1 <= N <= 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어집니다. 

 

출력 조건

 

• 첫째 줄에 최소 비교 횟수를 출력합니다. (21억이하) 

 

입력 예시 1

 

3
10
20
40

 

 

출력 예시 1

 

100

 

입력 예시 2

 

4
10
20
40
50

 

 

출력 예시 2

 

220

 

 

 

https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

 

 

---

 

 

문제 해설

 

정렬 문제인데 제한시간이 2초다. 큐안에 있는 요소 중 가장 최소의 값 2개를 꺼내서 합해야 한다. 필자는 생각나는 대로 코딩을 해서 vsc에서 돌려봤는데 책에 있는 테스트 케이스 2개는 통과했지만, 백준에 제출해보니 시간 초과가 나왔다. 책에서 제시하는 해설 코드와 필자가 만들어본 코드 2개를 모두 올려보겠다.

 

책에서 제시한 해설 코드는 다음과 같다. 

 

import heapq

n = int(input()) 

# 힙(heap)에 초기 카드 묶음을 모두 삽입
heap = []
for i in range(n): 
    data = int(input())
    heapq.heappush(heap, data) # heap리스트에 data를 넣는다.

result = 0

# 힙(heap)에 원소가 1개 남을 때까지
while len(heap) != 1: # 마지막 sum값이 남으면 끝. 
    # 가장 작은 2개의 카드 묶음 꺼내기
    one = heapq.heappop(heap) 
    two = heapq.heappop(heap) 
    # 카드 묶음을 합쳐서 다시 삽입
    sum = one + two
    result += sum
    heapq.heappush(heap, sum) 

print(result)

 

이 문제는 heap정렬을 이용해야 하는 문제다. 파이썬에서는 최소힙을 기본으로 제공하기 때문에 이 문제에 더욱 알맞다. 

 

heap정렬에 대해 간단하게 적고 가겠다. 

 

PriorityQueue를 이용하는 방법도 있지만, 코딩 테스트 환경에서는 heap 자료구조를 이용하는 것이 더 빠르게 동작하므로 heapq를 이용한다. 

 

heap 자료구조의 장점은 단순히 원소를 힙에 넣고 빼는것만으로도 시간 복잡도 O(NlogN)에 오름차순 정렬이 완료된다는 점이다. 

 

원소를 힙에 삽입할때는 heapq.heappush() 메서드를 사용하고, 힙에서 원소를 꺼낼 때는 heapq.heappop() 메서드를 사용한다. 

 

앞에서 파이썬의 heap 자료구조는 최소 힙을 기본으로 한다고 했는데 최소 힙에 대해 짧게 알아보자. 

min heap(최소 힙)

최소 힙의 정의는 다음과 같다. 

 

최소 힙 : 부모 노드의 키값이 항상 자식 노드의 키값보다 작은 경우 

 

특징: 최소 힙에서는 가장 낮은 값을 가진 노드가 항상 root의 자리에 오게 되고 정렬을 유지하게 된다.

 

*키 값의 대소관계는 부모 - 자식 간에만 적용되며, 형제 노드 간에는 적용되지 않는다. 

 

자~ 이제 해설 코드를 이해하기 위한 사전지식은 모두 설명했다. 해설 코드로 돌아가 보자. 

 

heap 자료구조를 사용하기 위해서 import heapq를 해주어야 한다. 

 

heap 이라는 이름의 리스트를 선언해 주고 이곳에 데이터를 넣을 것이다. 

 

for i in range(n):
    data = int(input())
    heapq.heappush(heap, data) # heap에 data를 넣는다.

 

3번째 줄에서 보듯이 (heap, data) 순서다. heap에 data를 넣는 의미로 heappush() 메서드는 이렇게 사용한다. 

 

while len(heap) != 1:

 

heap 리스트의 길이가 1이 될 때까지인 이유는 반복의 마지막에 heappush()를 사용해 원소를 하나씩 넣어주기 때문이다. 즉, 마지막 원소가 들어가면 반복을 멈추게 된다. 

 

one = heapq.heappop(heap) # heap에 있는 루트(root) 노드를 빼서 one(변수)에 넣는다. 
two = heapq.heappop(heap)  
sum = one + two

 

각각 가장 작은 원소(root원소)를 빼서 one, two 변수에 대입한다. 그리고 sum 변수에 둘을 합친다. 

 

sum = one + two 
result += sum
heapq.heappush(heap, sum) # heap에 비교값 sum을 넣는다.

 

비교값을비교 값을 다음 sum에 누적으로 더하기 위한 방법이다. 이렇게 다음 비교 값을 heap에 넣고 2개씩 최솟값을 빼주는 과정을 반복하다 보면, 마지막 2개로 만들어진 비교 값이(sum) heap에 들어가는 순간이 반복의 마지막이 된다. (len(heap) == 1 이 돼버림) 

 

다음은 필자가 heap 자료구조를 사용하지 않고 짜본 코드다.

 

n = int(input())
data = [] 
for i in range(n):
    a = int(input())
    data.append(a)

data.sort() # 정렬 
temp = data[0] 
result = 0 

for i in range(1, n):
    data.sort() # 새로 반복할때마다 다시 정렬
    temp += data[i] 
    result += temp
    
print(result)

 

앞에서도 말했지만, 이 코드는 시간 초과를 받았다. 두 번째 반복문에서 data.sort()를 계속 진행해 주는 게 아마 속도를 느리게 했을 거라 생각한다. 파이썬 기본 정렬은 O(NlogN)을 보장하지만 그것도 한두번 써야지 반복할 때마다 사용하면 부하가 어마어마할 것이다.