[Leetcode] 1769. Minimum Number of Operations to Move All Balls to Each Box

21-12-06
solved

Problem

You have n boxes. You are given a binary string boxes of length n, where boxes[i] is '0' if the ith box is empty, and '1' if it contains one ball.

In one operation, you can move one ball from a box to an adjacent box. Box i is adjacent to box j if abs(i - j) == 1. Note that after doing so, there may be more than one ball in some boxes.

Return an array answer of size n, where answer[i] is the minimum number of operations needed to move all the balls to the ith box.

Each answer[i] is calculated considering the initial state of the boxes.

문제 유형은 잘 모르겠다. 그냥 array인가보다. 오늘 daily challenge 문제, Q.1271가 easy 이길래, medium 하나 더 풀려고 challenge 문제와 연관된 문제를 풀었다. 사실 이 1769번도 acceptance가 되게 높은 축에 속한다.
이 문제를 brute force로 풀면 time complexity O(n^2)이 나오는데 O(n)이 나오는 것을 목표로 풀어보려고 했다.

Solution

class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        ans=[0]
        leftZero=0
        rightZero=0
        
        for i,v in enumerate(boxes):
            if v=="1": 
                ans[0]+=i
                rightZero+=1
        
        if boxes[0]=="1":
            leftZero=1
            rightZero-=1
        #print(ans)
        
        for i,v in enumerate(boxes[1:],start=1):
            #print(i,v)
            val=ans[-1]-rightZero+leftZero
            ans.append(val)
            
            if v=="1":
                leftZero+=1
                rightZero-=1
        
        return ans

스트링을 처음부터 끝까지 한 번 읽어서 ans[0]을 우선 먼저 계산한다. 그 다음 중요한 것은 iteration 과정에서 왼쪽에 있는 0의 개수(leftZero)와 오른쪽에 있는 0의 개수(rightZero)이다.

val=ans[-1]-rightZero+leftZero

이 부분이 가장 중요하다. iteration하는 문자 기준으로 오른쪽에 있는 0 개수만큼은 전체 거리가 가까워 지고, 왼쪽에 있는 0 개수만큼 전체 거리가 멀어지기 때문에 위와 같은 val이 결정된다.

for i,v in enumerate(boxes[1:],start=1):

개인적으로 기억하고 싶은 코드는 위 코드이다. enumerate할 때, index 1부터 읽고 싶을 때, 위와 같이 하면 된다.

Another Solution

class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        n = len(boxes)
        answer = [0] * n
        curr, steps = 0, 0
        for i in range(n):
            answer[i] += steps
            curr += int(boxes[i])
            steps += curr
        curr, steps = 0, 0
        for i in reversed(range(n)):
            answer[i] += steps
            curr += int(boxes[i])
            steps += curr
        return answer

자기보다 왼쪽에 있는 1 개수를 answer[i]에 담는다. 이 때, 1 개수는 누적되기 때문에, steps에 저장할 수 있다.(일종의 dp로 볼 수 있다.) O(N)이 소모된다.
이제 반대로 자기보다 오른쪽에 있는 1 개수를 answer에 저장한다. 이 과정도 O(N)이 소모된다.

한 번 정방향으로 읽었다가, 반대 방향으로 읽는 풀이가 종종 보인다. 기억해뒀다가, 나도 다음에 써먹어야겠다.

서버 만드는 과제하러 가야하는데, 많이 어렵다. 조금 막막하다. 차근차근 해내야겠다.