[구현, 그리디] 야근 지수 (Lv.3)
걸린 시간
40분
접근 방식
예시로 works가 [7,5,5,3,2]라고 한다면
일단 높은순대로 정렬하고
a = 0 부터 계산해서
a = 1 은 (a[0]-a[1])a 만큼 n을 누적한다.
[5,5,5,3,2] N = 2
a = 2 는 (a[1]-a[2])a 만큼 n을 누적한다.
[5,5,5,3,2] N = 2
a = 3 은 (a[2]-a[3])*a 만큼 n을 누적한다.
[3,3,3,3,2] N = 8
위 방법대로 높은수부터 천천히 줄여나간다.
이런식으로 N을 늘리다가 만약 N이 n을 넘으면 복구해야함
나머지 n-N 만큼 남은건 각각 1씩 줄여가면서 소모시키면 배열이 완성되고 그걸 각 요소들의 제곱들의 합으로 답을 구하면 된다.
정답 코드
def solution(n, works):
if sum(works) <= n:
return 0
answer = 0
works = sorted(works, reverse=True)
a = 1
N = 0
while a < len(works):
cost = (works[a-1] - works[a]) * a
if N + cost > n:
break
N += cost
a += 1
remain = n-N
base = remain//a
extra = remain%a
for i in range(a):
if i < extra:
works[i] = works[a-1]-base-1
else:
works[i] = works[a-1]-base
for i in works:
answer += i*i
return answer배운점
아이디어는 간단했지만 시간초과가 나지 않게 구현하는 것은 꽤나 복잡한 일이었다.
[구현, 그리디] 숫자 게임 (Lv.3)
걸린 시간
20분
접근 방식
가장 점수차가 낮게 이기도록 배치하는것 먼저 넣는 그리디 방식을 생각해보았다.
정답 코드
def solution(A, B):
answer = 0
start = 0
end = len(B)-1
A = sorted(A, reverse=True)
B = sorted(B, reverse=True)
for i in range(len(A)):
if A[i] < B[start]:
answer += 1
start += 1
else:
end -= 1
return answer배운점
배열에서 하나씩 빼는 pop()함수도 O(n)이기 때문에 투 포인터를 활용해서 계산하는 것이 시간초과가 나지 않는다.
