[LeetCode] 1769. Minimum Number of Operations to Move All Balls to Each Box (Python)

 

난이도: Medium

 

문제 설명 

---

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.

 

문제 예제

---

Example 1:

Input: boxes = "110"
Output: [1,1,3]
Explanation: The answer for each box is as follows:
1) First box: you will have to move one ball from the second box to the first box in one operation.
2) Second box: you will have to move one ball from the first box to the second box in one operation.
3) Third box: you will have to move one ball from the first box to the third box in two operations, and move one ball from the second box to the third box in one operation.

Example 2:

Input: boxes = "001011"
Output: [11,8,5,4,3,4]

 

제한 사항

---

• n == boxes.length
• 1 <= n <= 2000
• boxes[i] is either '0' or '1'.

 

Solution(솔루션)

class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        n = len(boxes)
        answer = [0 for _ in range(n)]

        for i in range(n):
            if boxes[i] == '1':
                for j in range(n):
                    answer[j] += abs(i-j)
        
        return answer

 

제한사항을 보니 최대 길이가 2000이라서 시간복잡도가 O(n^2)이어도 해결할 수 있을 것 같아 다음과 같이 작성했다.

 

2중 for문을 사용했는데 첫번째 for문에서는 boxes의 요소를 확인하면서 요소가 '1'인지 확인한다.

요소가 '1'이라고 하면 두번째 for문으로 넘어가 모든 다른 위치 j에 대해 abs(i-j)를 계산하고, answer[j]에 이를 더해준다.

 

마지막으로 answer를 return하여 정답을 맞출 수 있었다.

---

문제: 1769. Minimum Number of Operations to Move All Balls to Each Box

 

깃허브: github

algorithm_practice/LeetCode/1895-minimum-number-of-operations-to-move-all-balls-to-each-box at main · laewonJeong/algorithm_pra