517. Super Washing Machines

[zeikar]

Problem link

https://leetcode.com/problems/super-washing-machines/

Problem Summary

세탁기에 옷들이 있고 옷들을 한번에 하나씩 이동시킬 수 있을 때 모든 옷의 개수가 같게 만드는 최소 이동 횟수를 구하는 문제.

Solution

일단 전체 합이 개수의 배수가 되어야 하니 먼저 예외 처리를 해주고, 모든 세탁기의 옷은 합 / 개수가 되어야 한다.

여기서 간단하게 드는 생각은 가장 큰 값 - (합 / 개수) 하면 답일까? 싶은데 반례가 존재한다.
[0,0,2,2] 같은 경우 답은 2이다.

왜 2가 되었는가 잘 생각해보면 맨 왼쪽으로 옷을 이동시키려면 중간에 두번째 세탁기를 거쳐서 넘어가야 한다. 즉 두번째 세탁기를 채우기 위해서는 이전에서 필요한 옷들이 더 필요하게 된다. (총 2개가 필요함) 한번에 한칸씩만 옷이 이동해야 하므로 2번 이동해야 한다.

비슷한 반례로 [0,0,11,5]가 있는데 비슷하게 두번째 세탁기에 8개의 옷이 필요하므로 총 8번 이동해야 한다.

formal하게 써보자면 필요한 옷의 개수를 누적해서 더해가면서 이 값과 (가장 큰 값 - (합 / 개수)) 중 최대가 정답이다.

이를 for문을 돌면서 계산하면 정답이다.

솔루션 참고함

Source Code

class Solution:
    def findMinMoves(self, machines: List[int]) -> int:
        s, n = sum(machines), len(machines)
        if s % n != 0:
            return -1

        target = s // n
        ans = max(machines) - target
        needs = 0
        for m in machines:
            needs += m - target
            ans = max(ans, abs(needs))

        return ans