(Python/LV3) 야근지수

문제 출처:https://school.programmers.co.kr/learn/courses/30/lessons/12927

 

풀이:

첫 풀이

테스트 케이스는 다맞음 채점하면 20/100

def solution(n, works):
    work_sum = sum(works)
    list = []
    if n >= work_sum:
        return 0
    a, b = (work_sum - n) // len(works), (work_sum - n) % len(works)
    for i in range(len(works)):
        list.append(a)
    idx = len(list) - 1

    for i in range(b):
        list[idx] += 1
        idx -= 1
    return sum([i**2 for i in list])

 

두 번째 풀이:

heapq 최솟값구하는거를 거꾸로 생각하기로함 

93.3 / 100

 

import heapq
def solution(n, works):
    work_sum = sum(works)
    list = [-i for i in works]
    heapq.heapify(list)

    for i in range(n):
        x = heapq.heappop(list)
        x +=1
        heapq.heappush(list,x)

    return sum([i**2 for i in list])

 

정답코드:

import heapq
def solution(n, works):
    work_sum = sum(works)
    if work_sum< n:
        return 0

    list = [-i for i in works]
    heapq.heapify(list)

    for i in range(n):
        x = heapq.heappop(list)
        x += 1
        heapq.heappush(list,x)

    return sum([i**2 for i in list])

과정:

work_sum = sum(works)
if work_sum< n:
    return 0

sum은 메모리를 많이 잡아먹는다. 처음에 미리 해두고 선언

남은 일이 남은 퇴근시간보다 적으면 야근 안 해도 되니깐 0 리턴

 

list = [-i for i in works]
heapq.heapify(list)

list 를 - 를 붙여서 만든다 이유는 - 가 없이 heapify 하면 최댓값이 맨 위니깐 반대로

- 를 붙여주면 최솟값이다

 

for i in range(n):
    x = heapq.heappop(list)
    x += 1
    heapq.heappush(list,x)

n 만큼 돌면서

맨 왼쪽꺼를 pop 해주고 x 라 칭해놓음

그리고 x를 1을 더해주고

다시 heappush 해서 수정

이유는 heappush를 해줘야 맨 첫값(list[0] 맨 왼쪽값)이 계속 최솟값으로 유지되기 때문이다

 

return sum([i**2 for i in list])

어차피 음수도 제곱하면 양수이므로 안 건드리고 리턴

 

heapq 대신

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

이 방법도 있다,,, (시간초과는 나옴)