본문 바로가기
IT 이야기/알고리즘 공부

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

by Dblog 2021. 2. 3.
728x90

https://programmers.co.kr/learn/courses/30/lessons/12927

 

코딩테스트 연습 - 야근 지수

회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도

programmers.co.kr

 

문제가 개편되어 이제는 효율성도 체크합니다. 

아래 코드는 효율성을 체크하기 전 최댓값만 조금씩 빼는 문제 풀이입니다
※야근 지수가 요소의 제곱을 더하기 때문에 높은 값을 최대한 줄여야 지수가 낮아집니다.

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 모듈 사용법

Engineering Blog by Dale Seo

www.daleseo.com

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

728x90

댓글