[PCCP 실전모의고사 #2_02] 신입사원 교육

문제

신입사원 교육 (문제 보기)

• 산업 스파이 민수는 한 번에 2명의 직원을 뽑아 신입사원 교육을 시킨다. 이때 뽑힌 두 명의 신입사원은 개인의 능력치가 두 직원의 능력치의 합으로 갱신된다.
• 신입사원의 능력치를 담은 ability 배열과 교육 진행 횟수인 number 값이 주어진다. number 번의 교육 후, 신입사원의 능력치의 합이 최소가 되도록 하려고 한다. 이때 신입사원의 능력치 합의 최솟값을 구하라.

제한사항 및 입출력 예시

아이디어

💡 heapq를 사용한다

• 매번 가장 능력치가 적은 두 신입사원을 뽑아 더해줘야 하는데, 이때 일반 정렬(sort)를 사용하면 매 순간마다 정렬을 진행해야 하므로 시간복잡도가 커진다.
• 따라서 heapq를 사용해 신입사원의 능력치를 push, pop 할때마다 자동으로 정렬해줘 시간복잡도를 줄인다.

소스코드

import heapq
def solution(ability, number):    
    queue = []
    for a in ability:
        heapq.heappush(queue, a)
    
    for _ in range(number):
        x = heapq.heappop(queue)
        y = heapq.heappop(queue)
        new = x + y
        heapq.heappush(queue, new)
        heapq.heappush(queue, new)
    
    return sum(queue)

실행 결과