야근 지수

songjy6565·2019년 5월 14일
0

algorithm

목록 보기
27/50

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 같은 케이스만 와도 엄청 비효율적이게 동작하는 것이 보인다.;;
뭐 암튼 아니다 싶어서 다 지우고 좀 더 생각해봤는데 제법 간단하게 이분 탐색법이 적용될 수 있다는 것을 깨달았다.. 그 이후론 쉬운 내용이라 패스..

0개의 댓글