[programmers] 야근 지수 문제 - Python

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

프로그래머스

얼탱이 없이 풀어놓고 왜 안되나 생각했던 문제다.

---

 

works 의 남은 값들이 모두 같을 때 가장 지수가 낮다는 것은 금방 알 수 있었다.

이제 다음과 같은 얼탱이 없는 풀이를 제시했다.

def solution(n, works):

    total = sum(works)
    if n >= total:
        return 0

    total -= n
    Q, R = total // len(works), total % len(works)

    answer = 0
    for _ in range(R):
        answer += (Q+1)**2
    for _ in range(len(works)-R):
        answer += Q**2

    return answer

sum(works) 에 대해서 n 값을 빼준 남은 값들을 최대한 평평하게 펼친다는 개념이다. 제출 시 미칠듯한 붉은 글자들이 보인다.

works 가 [1,2,3,4] , n 이 1 이라고 가정하자. 위의 코드대로 하면 n 만큼 일하고 난 works 는 [2,2,2,3] 이 된다.

말도 안되는 결과다. 다시 풀어본다.

---

진짜 n 번 만큼 일을 하면된다. n 번만큼 반복하며 최댓값만 계속 1씩 줄여준다면 그게 평평하게 펼치는 것과 다를게 없다.

다만 매번 최댓값을 찾아내야 하므로 heapq 를 이용한다.

import heapq

def solution(n, works):

    answer = 0
    heap = []
    for work in works:
        heapq.heappush(heap, -1 * work)

    for _ in range(n):
        Max = heapq.heappop(heap)

        if not Max:
            return 0

        Max += 1
        heapq.heappush(heap, Max)

    for work in heap:
        answer += work**2

    return answer

간단하게 최댓값을 이용해서 풀어낼 수 있다.