728x90
https://programmers.co.kr/learn/courses/30/lessons/12927
문제가 개편되어 이제는 효율성도 체크합니다.
아래 코드는 효율성을 체크하기 전 최댓값만 조금씩 빼는 문제 풀이입니다
※야근 지수가 요소의 제곱을 더하기 때문에 높은 값을 최대한 줄여야 지수가 낮아집니다.
def solution(n, works):
answer = 0
if sum(works) < n:
return answer
else:
for i in range(n):
works = sorted(works,reverse=True)
works[0] -= 1
answer = list(map(lambda x : x ** 2 , works))
return sum(answer)
효율성을 체크하기 시작한 이후 엥간해선 효율성 체크가 성공하지 않습니다. 인터넷을 찾던 중 Max heap을 활용한 문제풀이가 있어 공유합니다.
import heapq
def solution(n, works):
answer = 0
heap=[]
for work in works:
heapq.heappush(heap, (-work, work))
while True:
if n==0:
break
work=heapq.heappop(heap)[1]-1
heapq.heappush(heap, (-work, work))
n-=1 #시간 감소
for h in heap:
if h[1] < 0:
continue
answer+=h[1]**2
return answer
heap 사용법
heapq 라이브러리는 추후에 공부해서 따로 게시글로 작성해보겠습니다.
728x90
'IT 이야기 > 알고리즘 공부' 카테고리의 다른 글
[Programmers][Python][2019 카카오 개발자 겨울 인턴십] 불량사용자 - level3 (0) | 2021.02.05 |
---|---|
[Programmers][Python][해시] 베스트앨범 - level3 (0) | 2021.02.05 |
Backjoon 1094번 막대기 (0) | 2020.12.01 |
Backjoon 1010번 다리놓기 (0) | 2020.11.30 |
[Programmers] 섬 연결하기 (0) | 2020.11.26 |
댓글