사용 언어 - Python3
문제 - 신입사원 교육
https://school.programmers.co.kr/learn/courses/15009/lessons/121688
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
정답
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)
레퍼런스
'Algorithm > 스택&큐&덱&힙' 카테고리의 다른 글
[프로그래머스 lv 2] 큰 수 만들기 (0) | 2023.12.19 |
---|---|
[프로그래머스] PCCP 모의고사 2회 3번 카페 확장 (1) | 2023.12.15 |
[프로그래머스] PCCP 모의고사 1회 4번 운영체제 (0) | 2023.12.14 |
[프로그래머스] PCCP 모의고사 1회 3번 유전법칙 (0) | 2023.12.14 |
[프로그래머스 lv 3] 이중우선순위큐 (0) | 2023.06.19 |
댓글