level1_명예의 전당(1)

 

내가 제출한 코드

def solution(k,score):
    anwser = [] # 최하위 점수 리스트
    
    hall = [] #점수 저장 리스트
    
    for i in score:
    	if (len(hall) < k):
        	hall.append(i)
        else:
        	if (i > min(hall)):
            	hall.append(i)
        
        hall.sort()
        answer.append(hall[0])
        
    return answer

• 최하위 점수 리스트(answer)와 명예의 전당 목록 점수 저장 리스트(hall)를 생성한다.
• if(len(hall) < k): hall.append(i)
  • 만약 명예의 전당에 올라갈 자리가 있으면 점수를 명예의 전당에 올린다(hall 리스트)
• else
  • 만약 명예의 전당 자리가 다 찼다면
•  if(i>min(hall))
  • 올릴 점수가 명예의 전당에서 가장 낮은 점수보다 큰 지 비교하고, 올릴점수가 더 크다면 
  • 명예의 전당에서 가장 낮은 점수를 제거하고
  • 새로운 점수를 올린다.
• hall.sort()
  • 명예의 전당에 있는 점수들을 오름차순으로 정렬하고
• answer.append(hall[0])
  • 가장 낮은 점수를 발표한다.

 

다른 사람이 제출한 코드 1

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

• score의 각 점수 s에 대하여 q리스트에 점수를 추가한다.
• 만약 q 리스트의 길이가 k를 초과한다면, q에서 가장 작은 값을 제거하여 상위 k개의 점수만 유지한다. 
• q 리스트의 최소값(min(q))을 answer에 추가한다. 

 

다른 사람이 제출한 코드 2

import heapq

def solution(k, score):
    max_heap = []  # 최대 힙 역할을 할 리스트
    answer = []    # 결과를 저장할 리스트

    for sc in score:
        # 최대 힙을 위해 (음수로 변환한 점수, 실제 점수) 형태로 힙에 추가
        heapq.heappush(max_heap, (-sc, sc))
        
        # max_heap에서 상위 k개의 요소 중에서 가장 큰 점수를 answer에 추가
        answer.append(max(heapq.nsmallest(k, max_heap))[1])

    return answer

• max_heap
  • 최대 힙처럼 사용할 빈 리스트로, 상위 k개의 점수를 관리한다.
• answer
  • 매 단계에서 상위 k개의 점수 중 가장 작은 점수를 저장할 리스트이다.
• for sc in score:
  • score 리스트의 각 점수 sc를 순차적으로 확인한다.
  • 매 단계에서 새로운 점수가 추가될 때마다 상위 k개의 점수를 업데이트한다.
• heapq.heappush(max_heap, (-sc, sc))
  • Python의 heapq는 기본적으로 최소 힙(min heap)으로 작동한다. 여기서는 최대 힙으로 사용하려고 점수를 음수로 변환하게 추가한다.
  • 가장 큰 점수가 가장 작은 음수로 처리되어 최대 힙처럼 사용할 수 있다.
  • 예를 들어 sc = 7이라면 (7,-7) 형태로 max_heap에 추가된다.
• answer.append(max(heapq.nsmallest(k, max_heap))[1])
  • heapq.nsmallest(k, max_heap)
    • max_heqp에서 가장 작은 k개의 요소를 반환한다.
    • max_heap은 음수로 변환된 점수들을 기준으로 구성되어 있어, nsmallest를 통해 사실상 상위 k개의 높은 점수들을 가져오는 셈이다.
  • max(heapq.nsmallest(k, max_heap))[1]
    • nsmallest로 상위 k개를 가져온 후, 이들 중 가장 큰 점수를 선택해 그 점수(sc 원래 값)를 answer 리스트에 추가합니다. 이 값이 상위 k개 점수 중 가장 작은 값이다.

예시)
k = 3이고, score = [10, 100, 20, 30, 50, 80, 90]인 경우
    1. score 리스트의 첫 번째 값 10을 max_heap에 추가 → max_heap = [(-10, 10)] → answer = [10]
    2. 두 번째 값 100 추가 → max_heap = [(-100, 100), (-10, 10)] → answer = [10, 10]
    3. 세 번째 값 20 추가 → max_heap = [(-100, 100), (-10, 10), (-20, 20)]
        → answer = [10, 10, 10]
    4. 네 번째 값 30 추가 → max_heap = [(-100, 100), (-30, 30), (-20, 20), (-10, 10)]에서
        상위 3개 중 가장 작은 20을 answer에 추가 → answer = [10, 10, 10, 20]

 위 예시로 풀어보면

 

문제 예시랑 다른 점 !!! 참고!!

 

참고 블로그

https://velog.io/@yeonsubaek/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%ED%9E%99%ED%81%90heapq-%EB%AA%A8%EB%93%88%EB%A1%9C-%ED%9E%99heap-%EB%8B%A4%EB%A3%A8%EA%B8%B0

[자료구조] 파이썬 힙큐(heapq) 모듈로 힙(heap) 다루기

https://newpower.tistory.com/113

heapq모듈에 있는 nlargeest(), nsmallest() 함수

 

 

 

최대 힙을 쓰는 이유는

큰 점수들을 우선시하여 상위 k개를 관리하고, 그 중 가장 작은 값을 빠르게 찾기 위함이다!