[프로그래머스] 명예의 전당 (1) (Python)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/138477

프로그래머스

소스 코드

import heapq
def solution(k, score):
    stage = []
    answer = []
    for idx in range(len(score)):
        # 리스트 내 원소를 대소비교하여 추가    
        heapq.heappush(stage,score[idx])
        # 리스트길이가 k 초과 시 최솟값 pop
        if len(stage) > k:
            heapq.heappop(stage)
        # 리스트의 최솟값 저장
        answer.append(stage[0])
    return answer

해설

• 힙을 이용한 최솟값 처리

힙

자료구조 중에 힙을 이용하면 간단히 풀 수 있는 문제였습니다.

아주 간단히 설명하자면 힙의 두 가지 기능을 이용할 수 있습니다.

 

1) heappush(리스트, 추가할 원소)

이 함수는 두 개의 인자를 받습니다.

리스트와 원소를 인자로 받아 그 리스트에 인자로 받은 원소를 추가해줍니다.

이때 이진 탐색을 수행하여 대소를 비교하고 적절한 위치에 추가가 됩니다.

import heapq

list = [1,3,4]
heapq.heappush(list,2)
print(list)
# [1, 2, 4, 3]

list = [1,4,3]
heapq.heappush(list,2)
print(list)
# [1, 2, 3, 4]

사실 힙은 지금까지 봤던 일반적인 리스트와 처리 방식이 다르기 때문에 위의 print 결과가 조금은 다르게 나타납니다.

간단히 어떻게 쓰는지만 알고 싶다면 굳이 이해할 필요는 없지만, 정확히 이해하고 싶다면 힙에 관한 다른 자료들을 찾아 보시는 걸 추천합니다.

아래는 참고할만한 블로그 게시물 링크입니다.

https://reakwon.tistory.com/42

[자료구조] 그림으로 쉽게 보는 힙(Heap) 개념과 코드

어쨌든 여기서의 핵심은 비어 있는 리스트에 대해 heappush로 원소를 채우면 오름차순 정렬이 된다는 것입니다.

 

2) heappop(리스트)

이 함수는 인자로 받는 리스트에서 최솟값을 뽑아내주는 함수입니다.

우리는 heappush를 통해서 정렬된 리스트를 만들어 주었으므로 그 리스트의 가장 작은 값, 즉 0번 인덱스에 해당하는 값이 추출될 것입니다.

 

명예의 전당에 오를 수 있는 최대 숫자 k를 초과하는 경우 리스트 내 최솟값을 뽑아내고,

리스트에 남은 가장 작은 값을 정답 리스트에 추가하면 되겠습니다.