프로그래머스 야근지수

문제 설명

회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다.Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요.

제한 사항

• works는 길이 1 이상, 20,000 이하인 배열입니다.
• works의 원소는 50000 이하인 자연수입니다.
• n은 1,000,000 이하인 자연수입니다.

입출력 예

works	n	result
[4, 3, 3]	4	12
[2, 1, 2]	1	6
[1,1]	3	0

입출력 예 설명

입출력 예 #1
n=4 일 때, 남은 일의 작업량이 [4, 3, 3] 이라면 야근 지수를 최소화하기 위해 4시간동안 일을 한 결과는 [2, 2, 2]입니다. 이 때 야근 지수는 22 + 22 + 22 = 12 입니다.

입출력 예 #2
n=1일 때, 남은 일의 작업량이 [2,1,2]라면 야근 지수를 최소화하기 위해 1시간동안 일을 한 결과는 [1,1,2]입니다. 야근지수는 12 + 12 + 22 = 6입니다.

입출력 예 #3

남은 작업량이 없으므로 피로도는 0입니다.

풀이

• 이거 처음에 ㅋㅋㅋ 평균이나 편차로 한방에 계산될까 싶어서 지지고 복다가 안되서
• 힙 써서 1씩 빼려고 했는데 효율성 검사 있길래 뭉쳐서 계산하는 방식으로 바꿨는데 자꾸 오류가 나...
• 왜지? 하면서 3시간 날렸는데 리스트를 heapq로 바꿔버리고 계속 지지고 볶은 거...
• 근데 heapq로 바꾸면 값을 넣을 때 마다 자동 정렬해줌. 그래서 값이 바뀌어서 계속 실패가 났다.
• 결국 heapify를 지우고, 리스트로 만들어서 풀었다.
• 알고리즘을 이것 저것 시도하면서 꼬이는 실수들이 점점 많아진다.
• 처음에 딱 정하면 그걸로만 풀고, 안될 때는 다 지우고 다시 짜야 하는데 코드 재활용하려다 보니 쉽게 할 수 있는 것도 자꾸 틀리는 것 같다.

import heapq # 필요없는 내용ㅋㅋㅋ

def solution(n, works):
    works.sort() # heapify(works)
    count_of_big, mods, answer = 1, 0, 0
    
    while n > 0:
        while len(works) > 1 and works[-1] == works[-2]: #큰 숫자 두 개가 같은 값이면 합체
            count_of_big += 1
            works.pop(-1)
        if len(works) == 1: break # 배열에 값이 한개 뿐일 경우
        changes = min(n // count_of_big, works[-1] - works[-2])
        if changes == 0: break
        works[-1] -= changes
        n -= changes * count_of_big
        
    for i in range(len(works)-1):
        answer += works[i]**2
        
    if n == 0:
        answer += count_of_big * works[-1]**2
    else: # 남은 시간이 있으면
        changes = n // count_of_big
        mods = n % count_of_big
        if mods == 0:
            works[-1] = max(0,works[-1] - changes)
            answer += count_of_big * works[-1] ** 2
        else:
            works[-1] = max(0,works[-1] - changes)
            answer += (count_of_big - mods) * works[-1] ** 2
            answer += (mods) * max(0,works[-1]-1) ** 2

    return answer

정확성  테스트
테스트 1 〉	통과 (0.02ms, 10.3MB)
테스트 2 〉	통과 (0.02ms, 10.2MB)
테스트 3 〉	통과 (0.01ms, 10.2MB)
테스트 4 〉	통과 (0.02ms, 10.2MB)
테스트 5 〉	통과 (0.01ms, 10.1MB)
테스트 6 〉	통과 (0.01ms, 10.4MB)
테스트 7 〉	통과 (0.02ms, 10.2MB)
테스트 8 〉	통과 (0.56ms, 10.3MB)
테스트 9 〉	통과 (0.65ms, 10.2MB)
테스트 10 〉	통과 (0.02ms, 10.4MB)
테스트 11 〉	통과 (0.01ms, 10.2MB)
테스트 12 〉	통과 (0.02ms, 10.1MB)
테스트 13 〉	통과 (0.02ms, 10.3MB)
효율성  테스트
테스트 1 〉	통과 (1.10ms, 10.2MB)
테스트 2 〉	통과 (0.98ms, 10.3MB)

• 코드는 짧지만 속도가 나지 않는 방식...

def solution(n, works):
    if n>=sum(works):
        return 0;

    while n > 0:
        works[works.index(max(works))] -= 1
        n -= 1

    answer = sum([w ** 2 for w in works])

    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.02ms, 10MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.01ms, 10.2MB)
테스트 4 〉	통과 (0.01ms, 10.1MB)
테스트 5 〉	통과 (0.01ms, 10.2MB)
테스트 6 〉	통과 (0.01ms, 10.3MB)
테스트 7 〉	통과 (0.01ms, 10.4MB)
테스트 8 〉	통과 (0.30ms, 10.1MB)
테스트 9 〉	통과 (0.94ms, 10.3MB)
테스트 10 〉	통과 (0.01ms, 10.3MB)
테스트 11 〉	통과 (0.01ms, 10.3MB)
테스트 12 〉	통과 (0.02ms, 10.1MB)
테스트 13 〉	통과 (0.00ms, 10.2MB)
효율성  테스트
테스트 1 〉	실패 (시간 초과)
테스트 2 〉	실패 (시간 초과)

• 이게 원래 테스트 목적에 맞는 코드, 최대힙 사용

from heapq import heapify, heappush, heappop
def solution(n, works):
    heapify(works := [-i for i in works])
    for i in range(min(n, abs(sum(works)))):
        heappush(works, heappop(works)+1)
    return sum([i*i for i in works])
    
정확성  테스트
테스트 1 〉	통과 (0.06ms, 10.2MB)
테스트 2 〉	통과 (0.02ms, 10.1MB)
테스트 3 〉	통과 (0.05ms, 10.2MB)
테스트 4 〉	통과 (0.07ms, 10.3MB)
테스트 5 〉	통과 (0.01ms, 10.1MB)
테스트 6 〉	통과 (0.06ms, 10.2MB)
테스트 7 〉	통과 (0.06ms, 10.3MB)
테스트 8 〉	통과 (0.13ms, 10.2MB)
테스트 9 〉	통과 (0.19ms, 10.3MB)
테스트 10 〉	통과 (0.01ms, 10.2MB)
테스트 11 〉	통과 (0.02ms, 10.1MB)
테스트 12 〉	통과 (0.01ms, 10.2MB)
테스트 13 〉	통과 (0.01ms, 10.1MB)
효율성  테스트
테스트 1 〉	통과 (305.75ms, 10.3MB)
테스트 2 〉	통과 (319.33ms, 10.2MB)

• 하지만 난 빠름을 추구한다규... ㅡ.ㅡ;
• 삽질 했지만 만족.