파이썬PS) 백준 14729 칠무해 - 최대힙 사용

 

 

파이썬PS) 백준 14729 칠무해 - 최대힙 사용

 

문제 링크 : https://www.acmicpc.net/problem/14729

제출 코드: https://www.acmicpc.net/source/45496454

 

14729번: 칠무해

 

 

 

 

0.

파이썬으로 풀 경우

단순하게 모든 입력값을 리스트에 append 하고 정렬하여 7개만 출력하는 방법으로도

제한시간내에 통과된 제출이 있었다.

 

그러나 학생 수의 입력 범위가 최대 10,000,000으로 매우 크고

출력 값은 최솟값 7개만 필요했으며, 

무엇보다 문제 레벨이 브론즈가 아닌 실버5 였기 때문에 

문제 의도에 맞추어 자료구조를 이용하여 해결하였다.

 

덕분에 다른 해결 코드에 비해 적은 메모리와 조금 빠른 시간으로 통과할 수 있었다. 

 

 

 

 

1. 최소힙

최소힙은 트리구조 기반의 자료구조이며, 트리 최상단(root node)에 최솟값이 위치함을 보장한다.

 

파이썬에서의 최소힙은 list로 표현되며 0번째 index 에 항상 최솟값이 위치하게 된다.

 

최소힙 예제 코드

 

[5, 89, 3, 1, 23, 7, 2] 의 정렬되지 않은 리스트를 힙 모듈을 이용하여 계속 pop하면(heapq.heappop)

최초 1회는 제일 앞에 있는 5가 나오지만,

첫 번째 pop 이후 리스트의 0번 index 에는 계속 최솟값이 위치하고, 

다음 pop 값들은 모두 리스트에 남아있는 요소 중 최솟값이다. 

 

heapq.heappop(리스트), heapq.heappush(리스트, 아이템) 문법으로 최소힙 pop과 push를 할 수 있다.

'리스트'는 앞서 선언되어 있어야 한다.

 

heapq.heapreplace(리스트, 아이템) 문법을 사용하면, 최소힙의 루트 값을 '아이템'으로 교체한다.

( heapq.heappop 이후 heapq.heappush 를 사용하는 것과 같은 효과이며 공식 문서에 따르면 heapreplace가 조금 더 효율적이라고 한다 )

 

 

 

 

2. 최대힙

파이썬에서는 최소힙만 구현되어 있고 최대힙은 구현되어 있지 않다.

그러나 모든 요소에 -1을 곱하는 방법으로 최대힙을 사용할 수 있다.

 

 

 

 

 

3. 문제 해결 아이디어

 

최초의 7명의 점수를 최대힙에 push 한다.

이후 입력받는 점수가 저장되어 있는 7명의 값보다 작다면 (입력받는 점수가 최대힙 루트 값보다 작다면)

최대힙의 루트를 꺼내고 입력 점수를 push 한다.

 

학생수에 상관없이 메모리에 저장되는 리스트의 길이는 항상 7을 유지한다.

 

입력을 모두 받았다면, 리스트에 남아있는 요소를 가장 작은 순서대로 꺼낸다.

 

 

 

 

4. 코드