[프로그래머스] PCCP 모의고사 2회 2번 신입사원 교육

사용 언어 - Python3

문제 - 신입사원 교육

https://school.programmers.co.kr/learn/courses/15009/lessons/121688

프로그래머스

 

정답

heapq 자동 정렬 기능 활용

시간초과 없이 구현하기가 포인트!

 

1. 첫번째 시도 (오답) 

모든 테스트에서 시간초과

from itertools import combinations

def solution(ability, number):
    idx = [i for i in range(len(ability))] # idx
    
    while number > 0 :
        two = 1e9
        for i in combinations(idx,2):
            if two > ability[i[0]]+ability[i[1]]: # 두사람의 능력치의 합이 더 작으면
                two = ability[i[0]]+ability[i[1]]
                a = i[0] # 두사람의 인덱스 저장
                b = i[1]
        ability[a], ability[b] = two, two
        number -= 1

    return sum(ability)

 

 

2. 두번째 시도 (오답)

8개의 테스트에서 시간초과

def solution(ability, number):
    while number > 0 :
        ability.sort()
        two = ability[0] + ability[1]
        ability[0], ability[1] = two, two
        number -= 1

    return sum(ability)

 

 

3. heapq를 이용하는 방법

queue = []

능력치를 queue에 heappush해준다. (자동정렬됨)

x = 가장 왼쪽, 작은 능력치 heappop

y = 가장 왼쪽, 작은 능력치 heappop

x+y를 2번 heappush

import heapq
def solution(ability, number):
    queue = [] # 신입사원들의 능력치
    for a in ability:
        heapq.heappush(queue,a) #push,pop할때마다 자동정렬 => 시간복잡도 감소
          
    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)

 

 

 

 

 

레퍼런스