728x90
반응형
문제 출처: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
이 방법도 있다,,, (시간초과는 나옴)
반응형
댓글