[야근 지수/LV3/Python3]

프로그래머스 야근 지수 LV3

 

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

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


입출력 예

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

 

 

정확도 및 효율성 테스트가 존재한다.

다른 사람의 풀이를 보니 효율성 테스트가 여유로운 편이다. 

 

문제는 탐욕적인 방법으로 풀이가 가능하다.

현재 작업량 중 가장 큰 작업량을 줄이는 것이 가장 유리하기 때문이다.

이때 가장 큰 작업량을 찾기 위해서 우선순위 큐를 사용하였으며, 시간 복잡도를 줄이기 위해 2가지 방법을 준비했다.

 

1. 항상 n번 pop과 push를 진행해서 풀이하는 방법

import heapq
def solution(n, works):
    hq = []
    # 최대 힙으로 변경
    for v in works:
        heapq.heappush(hq, -v)
    
    while n>0:
        heapq.heappush(hq, heapq.heappop(hq)+1)
        n -= 1
    
    result = 0
    for v in hq:
        if v >= 0: continue
        result += v * v
    return result

우선순위 큐는 0번째 인덱스에 항상 최솟값을 유지하며 O(logN) 시간 복잡도에  삽입과 삭제를 지원한다.  

이때 N은 자료의 개수로, works의 개수가 그에 해당된다.   len(works)

퇴근까지 남은 시간 전부를 진행하기 때문에 최종적인 시간 복잡도는 O(n * log len(works))가 된다

효율성 테스트 통과 결과

 

 

 

 

 

2. pop만 진행해서 구하는 방법

import heapq
def solution(n, works):
    hq = []
    heapq.heapify(hq := [-i for i in works])
    # 최대 힙으로 변경
    
    temp, cnt, result = heapq.heappop(hq), 1, 0
    
    while n>0 and hq:
        if cnt == n:
            result += (temp+1) * (temp+1) * cnt
            break
            
        if (hq[0] - temp) * cnt > n:
            mok, namosi = n // cnt, n % cnt
            temp += mok
            result += ((temp + 1) * (temp + 1) * namosi) + (temp * temp * (cnt - namosi))
            break
            
        if temp == hq[0]:
            cnt += 1
            heapq.heappop(hq)
            continue
        
        n -= (hq[0] - temp) * cnt
        if n <= cnt:
            result += (hq[0] * hq[0] * (cnt-n)) + ((hq[0]+1) * (hq[0]+1) * n)
            break

        temp, cnt = hq[0], cnt+1
        heapq.heappop(hq)
        
    else:
        if n != 0:
            if (-temp) * cnt > n:
                mok, namosi = n // cnt, n % cnt
                temp += mok
                result += ((temp + 1) * (temp + 1) * namosi) + (temp * temp * (cnt - namosi))
        else:
            result += temp * temp * cnt  
            
    for v in hq:
        result += v*v
    return result

효율성 테스트 통과 결과

 

보다 더 나은 결과를 도출하기 위해 추가적인 변수를 사용했다.

temp와 cnt는 각각 현재까지의 최대 원소, 해당 원소의 개수를 의미한다.

 

1번 풀이의 hq 원소를 살펴보면 최댓값과 동일한 값이 점점 많아지게된다.

단순히 가장 큰 원소에서 1 뺀 값을 다시 넣으므로, 이 과정에서 동일한 값이 많아지게 되는 것이다.

해당 값을 hq에 다시 넣는 것이 아닌, 개수와 값만 저장해두어 후의 계산에 바로 쓰는 방식으로 택했다.

 

필요한 작업 시간은 (현재 저장된 최댓값과 hq에서 꺼낸 값의 편차) * 최댓값의 개수로 구할 수 있다.  (hq[0]  - temp) * cnt

 

필요한 작업 시간이 남은 작업 시간보다 많을 때

남은 작업 시간을 최댓값의 개수의 원소에 공평하게 분배해야하기 때문에 몫과 나머지를 이용했다. n//cnt, n%cnt

최댓값에 몫만큼 뺀 값에서 나머지 개수 만큼은 +1을 해서 계산을 하고, 그 외는 해당 값으로 계산을 진행했다.

result += ((temp + 1) * (temp + 1) * namosi) + (temp * temp * (cnt - namosi))

 

필요한 작업 시간이 남은 작업 시간보다 적을 때

1. 남은 시간을 갱신한다.
2. 최댓값과 최댓값의 개수를 갱신한다. 

3. 이전 행동을 반복한다.

 

남은 시간을 갱신하는 과정에서 남은 시간이 최댓값의 개수보다 적은 경우가 생기기도 한다.

이때는 남은 시간의 개수만큼 최댓값+1의 결과에 더하고, (최댓값의 개수 - 남은 시간)만큼은 최댓값 그대로 결과에 더한다.

result += (hq[0] * hq[0] * (cnt-n)) + ((hq[0]+1) * (hq[0]+1) * n)

 

 

최종적으로 hq에 남은 값들을 결과값에 더하면 답을 구할 수 있다.

---

 

최대힙을 만들기 위해 -연산을 했음에 주의해야 한다.

시간 복잡도의 경우 매우 널널한 편이니 간단히 구현해도 전혀 문제가 없다!