1769. Minimum Number of Operations to Move All Balls to Each Box(JAVA)

출처 : https://leetcode.com/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/description/?envType=daily-question&envId=2025-01-06

 

#문제 

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.
 

n개의 상자가 있습니다. 길이가 n인 이진 문자열 boxes가 주어지며, boxes[i]가 '0'이면 i번째 상자는 비어 있고, '1'이면 공이 하나 들어 있다는 것을 의미합니다.
한 번의 작업에서, 공 하나를 인접한 상자로 이동할 수 있습니다. 상자 i와 상자 j가 인접하다는 것은 ∣i−j∣=1|i - j| = 1∣i−j∣=1인 경우를 말합니다. 공을 이동한 후에는 어떤 상자에 공이 여러 개 있을 수도 있습니다.
각 상자에 대해 모든 공을 그 상자로 옮기는 데 필요한 최소 작업 수를 계산하여 크기가 n인 배열 answer를 반환하세요.
answer[i]는 상자들의 초기 상태를 고려하여 모든 공을 i번째 상자로 옮기는 데 필요한 최소 작업 수를 나타냅니다.

 

접근1 :  완전탐색

문자열의 각각의 위치에서 공의 위치를 탐색하고 더해준다

public class Solution {
    public int[] minOperations(String boxes) {
        int n = boxes.length();
        int[] res= new int[n];
        char[] c = boxes.toCharArray();
        for(int i  = 0 ;i< n ;i++){
            int left = i - 1;
            int right = i+1;
            while(left >= 0){
                if(c[left] =='1'){
                    res[i]+=(i - left);
                }
                left--;
            }
            while(right < n){
                if(c[right] =='1'){
                    res[i]+=(right-i);
                }
                right++;
            }
        }

        return res;
    }
}

 

접근2 : 누적계산

왼쪽, 오른쪽 공의 갯수를 통해서 현재위치에서 왼쪽에있는 공과 오른쪽의 공과의 거리를 계산

 

예를 들어 왼쪽에 공이 n개 존재한다면 다음 문자로 이동했을때 다음 문자로부터 왼쪽 공들과의 거리는 총 n만큼 늘어난다. 오른쪽은 공이 k개있을때 다음 문자로부터 오른쪽 공들과의 거리는 총 k만큼 줄어든다.

 

public class Solution {
    public int[] minOperations(String boxes) {
        int n = boxes.length();
        int[] res= new int[n];
        char[] c = boxes.toCharArray();
        //왼쪽 공의 갯수
        int left = 0;
        //오른쪽 공의 갯수
        int right = 0;
        int rdis = 0;
        int ldis = 0;
        for(int i = 0 ; i < n ;i++){
            if(c[i] == '1'){
                rdis+=i;
                right++;
            }
        }
        for(int i = 0 ; i<n;i++){
            res[i] = rdis + ldis;
            //현재 박스에 공이있다며 다음위치에서 왼쪽공이 1개 늘어나야함
            if(c[i] == '1'){
                left++;
                right--;
            }
            rdis = rdis - right;
            ldis = ldis + left;
        }

        return res;
    }
}