[PCCP 모의고사#2] 신입사원 교육 (우선순위큐)

문제 설명

산업스파이 민수는 A회사에 위장 취업했습니다. 이를 모르는 민수의 상사는 신입사원 교육 중 일부를 민수에게 맡겼습니다. 민수가 맡은 임무는 신입사원 중 2명을 선발하고 선발된 2명이 같이 공부하게 하는 것입니다. 모든 신입사원들의 능력치는 정수로 표현되어 있는데, 2명의 신입사원이 같이 공부하면 서로의 능력을 흡수하여 두 신입사원의 능력치는 공부 전 두 사람의 능력치의 합이 됩니다. 즉, 능력치가 3과 7인 두 사원이 같이 공부하면 두 사원의 능력치가 모두 10이 됩니다. 선발한 2인의 교육이 끝나면 민수는 다시 2인을 선발하여 교육을 진행할 수도 있습니다. 이때 한번 민수에게 선발된 사원이 다시 선발될 수도 있습니다. 민수가 교육한 신입사원들을 제외한 다른 신입사원들의 능력치는 변하지 않습니다.

민수는 산업스파이이기 때문에 교육 후 모든 신입사원들의 능력치의 합을 최소화하고 싶습니다. 예를 들어, 신입사원들의 능력치가 순서대로 10, 3, 7, 2이며, 민수가 2번 교육을 해야 한다면, 첫 번째 교육은 두 번째 사원과 네 번째 사원을 선발하면 두 사원의 능력치가 5가 되어 신입사원들의 능력치가 10, 5, 7, 5가 됩니다. 두 번째 교육도 두 번째 사원과 네 번째 사원을 선발하면 신입사원들의 능력치는 순서대로 10, 10, 7, 10이 됩니다. 이 경우가 교육 후 모든 신입사원들의 능력치의 합이 37로 최소가 되는 경우입니다.

신입사원들의 능력치를 나타내는 정수 배열 ability와 민수가 교육을 진행해야 하는 횟수를 나타내는 정수 number가 주어졌을 때, 교육 후 모든 신입사원들의 능력치의 합의 최솟값을 return 하는 solution 함수를 완성하세요.

제한 사항

• 2 ≤ ability의 길이 ≤ 1,000,000
• 1 ≤ ability의 원소 ≤ 100
• 1 ≤ number ≤ 10,000
• return 값이 10억 이하가 되도록 ability와 number가 주어집니다.

입출력 예

ability	number	result
[10, 3, 7, 2]	2	37
[1, 2, 3, 4]	3	26

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

• 첫 번째 사원과 두 번째 사원을 선발하여 공부를 시킨 후, 세 번째 사원과 네 번째 사원을 선발하여 공부를 시킵니다. 그 후 첫 번째 사원과 두 번째 사원을 한번 더 선발해 공부를 시키면, 신입사원들의 능력치는 순서대로 6, 6, 7, 7이 되고, 이때가 능력치의 합이 최소인 26이 됩니다.

풀이

• 이건 ability 배열을 작은 값으로 정렬하고, 작은 값 두개를 빼서, 합을 두번 넣어주는 일을 number 만큼 반복하면 된다.
• 근데 우선순위큐를 쓰면 넣을 때 부터 정렬되어 있으니까 정렬할 필요가 없고, 넣어줄 때도 자동정렬이 된다.
• 속도가 느리네. 힙큐 쓸 걸 그랬나... 힙큐 명령어가 길어서 귀찮....

from queue import PriorityQueue

def solution(ability, number):
    answer = 0
    pq = PriorityQueue()
    
    for i in ability:
        pq.put(i)
    for i in range(number):
        a = pq.get()
        b = pq.get()
        pq.put(a+b)
        pq.put(a+b)
    
    while pq.empty() != True:
        answer += pq.get()
        
    return answer

정확성  테스트
테스트 1 〉	통과 (983.50ms, 14.8MB)
테스트 2 〉	통과 (2973.13ms, 24.9MB)
테스트 3 〉	통과 (2994.13ms, 25.6MB)
테스트 4 〉	통과 (1391.92ms, 17.3MB)
테스트 5 〉	통과 (3322.82ms, 24.8MB)
테스트 6 〉	통과 (506.97ms, 12.8MB)
테스트 7 〉	통과 (650.27ms, 13MB)
테스트 8 〉	통과 (2682.30ms, 19.8MB)
테스트 9 〉	통과 (3598.64ms, 24.9MB)
테스트 10 〉	통과 (832.36ms, 13.4MB)
테스트 11 〉	통과 (3692.37ms, 27MB)
테스트 12 〉	통과 (3764.67ms, 27MB)

• 힙큐 명령어 긴건 이렇게 줄일 수 있긴 하구나...
• 힙큐로 바꾸니까 개빨라지네 ㅋㅋㅋ

from heapq import heapify as heapify, heappush as push, heappop as pop

def solution(ability, number):
    heapify(ability)
    
    for i in range(number):
        a = pop(ability)
        b = pop(ability)
        push(ability, a + b)
        push(ability, a + b)
        
    return sum(ability)

정확성  테스트
테스트 1 〉	통과 (12.13ms, 12.3MB)
테스트 2 〉	통과 (42.94ms, 17.5MB)
테스트 3 〉	통과 (41.95ms, 17.9MB)
테스트 4 〉	통과 (21.94ms, 13.4MB)
테스트 5 〉	통과 (46.49ms, 17.3MB)
테스트 6 〉	통과 (10.28ms, 11.3MB)
테스트 7 〉	통과 (13.80ms, 11.3MB)
테스트 8 〉	통과 (35.87ms, 15MB)
테스트 9 〉	통과 (36.66ms, 17.3MB)
테스트 10 〉	통과 (23.78ms, 11.7MB)
테스트 11 〉	통과 (41.90ms, 18.6MB)
테스트 12 〉	통과 (47.33ms, 18.6MB)