프로그래머스 - 명예의 전당(1) 파이썬

문제 

프로그래머스

 

풀이 

 

1. 힙을 이용한 풀이 

1. 점수 리스트를 힙에 추가 
2. 힙 자료구조의 원소의 개수 > k일 경우 힙 구조에서 점수가 가장 낮은 원소의 값을 제거 

from heapq import heappop, heappush

def solution(k, score):
    answer = []
    heap = []
    for s in score:
        heappush(heap, s)
        if len(heap) > k:
        #힙 불변성을 유지하면서, heap에서 가장 작은 항목을 팝하고 반환
            heappop(heap)
        answer.append(heap[0])
    return answer

힙의 특징 

- 힙은 자료구조 내부의 가장 큰 원소, 가장 작은 원소를 빠르게 찾아내는 것이 가능 
- 최대 힙과 최소 힙 두 종류가 있음 
- 우선순위 큐를 위해 만들어진 자료구조 
- 우선순위 큐: 데이터들이 우선순위를 갖고 있고 우선순위가 높은 데이터가 먼저 나감 

 

 

 

2. 문자열을 이용한 풀이 

1. 점수 리스트에서 꺼내온 값을 새로운 배열에 넣고 
2. 배열의 길이가 k보다 길어지면 가장 작은 기존 원소를 삭제 
3. 가장 작은 것을 answer에 추가 

def solution(k, score):
    q = []
    answer = []
    
    for s in score:
        q.append(s)
        if (len(q) > k):
            q.remove(min(q))
        answer.append(min(q))

    return answer