https://programmers.co.kr/learn/courses/30/lessons/12927
- flow
처음에 생각을 짧게 해서 (Sum % leng) (Sum//leng + 1)^2 + (leng - Sum % leng) (Sum//leng)^2 이런 공식 (sum == sum(works)-n, leng == len(works)) 이 적용되나 했는데 n이 작고 works 간 element 값들의 차이가 크면 당연히 틀리게 되서 ㅋㅋ 그러한 예외케이스에 매몰되다 보니 다음 코드도 되게 비효율적이게 짜게 되었다. 어떤 방법이었냐면 works를 reverse sort 해놓고 첫번째 element와 두번째 element 간 차이만큼 빼면서 위치 바꾸고 나아가는 방법이었다..
def solution(n, works):
answer = 0
works.sort(reverse=True)
while n > 0:
if len(works) == 1:
if n > works[0]:
works.pop(0)
break
else:
works[0] -= n
n = 0
if n < works[0]-works[1]+1:
works[0] -= n
n = 0
else:
cur = works[1]-1
n -= (works[0]-works[1]+1)
if cur == 0:
works.pop(0)
else:
for j in range(1,len(works)):
if works[j] > cur:
works[j-1] = works[j]
if j == len(works)-1:
works[j] = cur
else:
works[j-1] = cur
break
for k in range(len(works)):
answer += works[k]**2
return answer
지금 보면 단순히 (10001,10000,1) n=5000 같은 케이스만 와도 엄청 비효율적이게 동작하는 것이 보인다.;;
뭐 암튼 아니다 싶어서 다 지우고 좀 더 생각해봤는데 제법 간단하게 이분 탐색법이 적용될 수 있다는 것을 깨달았다.. 그 이후론 쉬운 내용이라 패스..
