[Programmers][Python][연습문제] 야근지수 - level3

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

※velog.io/@daon9apples/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Level3-%EC%95%BC%EA%B7%BC-%EC%A7%80%EC%88%98-Python

 

 

 

heap 사용법

www.daleseo.com/python-heapq/

[파이썬] heapq 모듈 사용법

heapq 라이브러리는 추후에 공부해서 따로 게시글로 작성해보겠습니다.