[프로그래머스] 야근 지수 - Python

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

프로그래머스

---

• 실패1 - 가장 많이 남은 작업량 1만큼 처리
  • 효율성 시간초과로 실패 
  • .sort()는 시간복잡도가 최악의 경우 O(nlogn)이다 

def solution(n, works):
    for _ in range(n):
        works.sort(reverse=True)
        if works[0] > 0:
            works[0] -= 1
        else:
            break
    return sum([i**2 for i in works])

 

• 실패2
  • 효율성 테스트 실패 
  • .index() 시간복잡도 : O(n)
  • max() 시간복잡도 : O(n)

def solution(n, works):
    while n > 0:
        idx = works.index(max(works))
        if works[idx] <= 0:
            break
        works[idx] -= 1
        n -= 1
    return sum([i**2 for i in works if i > 0])

 

• 성공
  • n이 최대 100만이니 O(n)까지 가능
  • 정렬을 하거나 최댓값을 찾으면 O(n^2)이 되므로
  • heapq 사용
    • heapq.heapqpop(list)을 하면 list의 최솟값을 pop함

import heapq
def solution(n, works):
    # 야근 X
    if n >= sum(works):
        return 0
    
    # heapq는 최솟값을 pop해줌
    works = [-i for i in works]
    heapq.heapify(works)
    for _ in range(n):
        w = heapq.heappop(works)
        heapq.heappush(works,w+1)
    # 야근 피로도
    return sum([i**2 for i in works])