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

 문제

 

 

 

 

 문제 상황

 

- works에 존재하는 숫자들은 남은 업무량을 의미하고 야근 지수는 이 숫자들의 제곱의 합을 의미한다. 즉, works에 존재하는 요소들에서 n 만큼을 제거하여 각 요소의 제곱의 합을 계산한 결과가 최소가 되게 한다.

 

 해결 전략

 

 

- works의 길이가 20,000 이므로 O(N^2)면 400,000,000(4억)의 연산이 된다. 즉 N^2는 시간 초과가 날 가능성이 높다. 최대 NlogN안에서 해결해야한다.

 

 

 

 코드

 

# 성공한 코드

def solution(n,works):
    # 요소를 다 합친 값보다 줄일 수 있는 값이 더크면 결국 모두 0이 된다.
    if sum(works) <= n:
        return 0
    works.sort(reverse = True)
    for i in range(len(works)-1):
        # 같은 값들과 안같은 값의 경계 차이
        diff = works[i] - works[i+1]
        # n이 i+1개 요소를 바꾸는 것보다 더 크면 i+1개의 요소를 
        # i+2 요소와 같은 숫자로 전부 바꿔준다.
        if diff*(i+1) < n:
            works[:i+1] = [works[i+1] for _ in range(i+1)]
            n -= diff*(i+1)
        # 만약 i+1개의 요소를 다 바꿀만큼 n이 남지 않았다면
        else :
            q, r = divmod(n, (i+1))
            # 뺄 수 있는 만큼 최대한 똑같이 뺀다.
            works[:i+1] = [works[j]-q for j in range(i+1)]
            # 남은 숫자만큼 빼는데 어차피 이 때에는 정렬상태가 중요하지 않으므로 
            # 그냥 r개를 뺀다.
            works[:r] = [works[j]-1 for j in range(r)]
            # n만큼 다 뺐으므로 n을 초기화
            n = 0
            break
    # 모든 요소가 같을 경우 위를 돌아도 n이 제거되지 않는다(차이를 기반으로 하므로)    
    if n != 0:
        # 공평하게 다 빼주고 남은 요소를 제거한다.
        q2, r2 = divmod(n, len(works))
        works = [works[idx]-q2 for idx in range(len(works))]
        works[:r2] = [works[j]-1 for j in range(r2)]
    result = 0
    for i in range(len(works)):
        result += (works[i])**2
    return result

 

# 실패한 Heap 풀이

import heapq
def solution(n,works):
    # 최소힙을 활용하여 최대값을 출력하기위해 -1을 곱하였다.
    for i in range(len(works)):
        works[i] *= -1
    # works를 heap 구조로 만든다.
    heapq.heapify(works)
    while True:
        if sum(works) == 0:
            return 0
        temp = heapq.heappop(works)
        heapq.heappush(works, temp+1)
        n -=1
        if n == 0:
            break
    print(works)
    late_work = 0
    for i in range(len(works)):
        late_work += (works[i])**2
    return late_work
 

 

 

 해설

 

- 처음에는heap을 이용해서 풀이하였다. heapify가 O(NlogN)의 속도이고 pop역시 O(logN)의 속도라 최대 O(NlogN)으로 생각했는데 속도 이슈가 발생하였다. 아직도 이유는 잘 모르겠다.

 

- 오히려 스킬적으로 접근하다보니 그냥 논리적으로 해결하면 될 문제를 더 고민하게 되었다. 오히려 수학적 접근이 풀이에 도움되는 경우가 프로그래머스 lv3에 더 많은 것 같다.

 

- 순회하면서 차이를 줄이며 리스트를 조절하는 방식으로 문제를 해결한다.

 

 

 

 새로 학습한 것 & 실수 

 

- 힙은 일종의 트리로 수의 집합에서 가장 작은 수나 가장 큰 수만을 자주 꺼내올때 유용한 자료구조다.

 

 

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