Lv.1 명예의 전당 (1)

문제

명예의 전당 목록의 점수의 개수 k, 1일부터 마지막 날까지 출연한 가수들의 점수인 score가 주어졌을 때, 매일 발표된 명예의 전당의 최하위 점수를 return하는 solution 함수를 완성해주세요.

제한사항

3 ≤ k ≤ 100
7 ≤ score의 길이 ≤ 1,000
0 ≤ score[i] ≤ 2,000

예제

나의 풀이

def solution(k, score):
    answer = []
    chart = []
    for i in score:
        chart.append(i)
        chart.sort(reverse = True)
        if len(chart) <= k:
        	answer.append(chart[-1])
        else:
            chart.pop()
            answer.append(chart[-1])
            
    return answer

다른 풀이

다른 풀이 코드를 보니까 heapq를 활용한 풀이가 많아서 공부할 겸 코드를 남겨놓는다.

import heapq

def solution(k, scores):
    
    honor = []
    prese = []
    
    for score in scores:
        heapq.heappush(honor, score)
        if len(honor) > k:
            heapq.heappop(honor)
        prese.append(honor[0])
    
    return prese

끄적끄적

heapq

heapq는 파이썬에서 힙(heap) 자료구조를 구현한 모듈이다. 힙은 우선순위 큐를 구현하는 데 사용되는 자료구조로, 특정 우선순위에 따라 빠르게 최소값 또는 최대값을 찾을 수 있게 해준다.
기본적으로 최소 힙(min-heap) 을 구현하며, 최소 힙에서는 부모 노드가 자식 노드보다 항상 작거나 같아야 하는 특성을 가진다.

최소 힙

부모 노드의 값이 자식 노드의 값보다 항상 작다. 따라서 가장 작은 값은 항상 루트 노드에 위치한다.

최대 힙

heapq는 기본적으로 최소 힙만 지원하지만, 최대 힙을 구현하고자 할 때는 음수 값을 사용하여 변형할 수 있다.

사용법

1.heapq.heappush(heap, item): 주어진 리스트 heap에 item을 추가한다. 리스트는 힙의 특성을 유지하도록 자동 정렬된다.

import heapq
heap = []
heapq.heappush(heap, 10)
heapq.heappush(heap, 5)
heapq.heappush(heap, 20)
print(heap)  # [5, 10, 20] (최소 힙)

2.heapq.heappop(heap): 힙에서 가장 작은 값을 제거하고 반환한다. 최소 힙에서는 가장 작은 값이 항상 루트 노드에 위치한다.

import heapq
heap = [5, 10, 20]
min_val = heapq.heappop(heap)
print(min_val)  # 5
print(heap)  # [10, 20]

3.heapq.hepify(iterable): 주어진 iterable을 힙 구조로 변환한다. 이 함수는 O(n)의 시간 복잡도를 갖는다.

import heapq
nums = [10, 20, 5, 30, 15]
heapq.heapify(nums)
print(nums)  # [5, 15, 10, 30, 20] (최소 힙으로 변환됨)

4.heapq.nlargest(n, iterable): iterable에서 가장 큰 n개의 원소를 내림차순으로 반환한다.

import heapq
nums = [10, 20, 5, 30, 15]
largest = heapq.nlargest(3, nums)
print(largest)  # [30, 20, 15]

5.heapq.nsmallest(n, iterable): iterable에서 가장 작은 n개의 원소를 오름차순으로 반환한다.

import heapq
nums = [10, 20, 5, 30, 15]
smallest = heapq.nsmallest(3, nums)
print(smallest)  # [5, 10, 15]

6.최대 힙 구현: heapq는 기본적으로 최소 힙이지만, 최대 힙을 구현하려면 삽입되는 값을 음수로 변환하여 사용한다.

import heapq
nums = [10, 20, 5, 30, 15]
max_heap = [-x for x in nums]  # 모든 값을 음수로 변환
heapq.heapify(max_heap)
largest = -heapq.heappop(max_heap)  # 음수로 저장된 값에서 최댓값을 반환하려면 다시 음수로 변환
print(largest)  # 30

heapq.heapify()와 sorted()

heapq.heapify()

• 리스트를 힙 구조로 변환하는 함수
• 시간 복잡도: O(n)
• 최소값/최대값을 자주 꺼내야 하는 경우
• 실시간으로 데이터를 처리해야 할 때: 예를 들어, 온라인 알고리즘에서 데이터 흐름에 따라 실시간으로 우선순위가 높은 항목을 처리해야 할 때 좋음

sorted()

• 퀵 정렬이나 병합 정렬 같은 알고리즘을 사용하여 리스트를 정렬하는 방식
• 시간 복잡도: O(n long n)
• 전체 리스트를 한 번에 정렬해야 하는 경우
• 정렬된 순서로 데이터를 다룰 때