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

문제 링크


내 코드

개수 세기 + 약간 생각.

2ms, 12.48MB

class Solution {
public:
    vector<int> minOperations(string boxes) {
        int lCnt{}, lSum{}, rCnt{}, rSum{};

        int n = boxes.size();
        for(int i{1};i<n;++i) {
            if(boxes[i] == '1') {
                ++rCnt;
                rSum += i; // rSum += rCnt (?)
            }
        }

        vector<int> answer;
        answer.push_back(rSum);

        if(boxes[0] == '1') {
            lCnt = 1, lSum = 1;
        }
        for(int i{1};i<n;++i) {
            rSum -= rCnt;
            if(boxes[i] == '1') {
                --rCnt;
            }

            answer.push_back(lSum + rSum);

            if(boxes[i] == '1') {
                ++lCnt;
            }
            lSum += lCnt;
        }

        return answer;
    }
};

Solution

Approach 1: Brute Force

  • 51ms, 11.97MB
  • Complexity
    • Let nn be the size of the string boxes.
    • Time Complexity: O(n2)O(n^2)
    • Space Complexity: O(1)O(1)
class Solution {
public:
    vector<int> minOperations(string boxes) {
        vector<int> answer(boxes.length());
        for (int currentBox = 0; currentBox < boxes.length(); currentBox++) {
            // If the current box contains a ball, calculate the number of moves
            // for every box.
            if (boxes[currentBox] == '1') {
                for (int newPosition = 0; newPosition < boxes.length();
                     newPosition++) {
                    answer[newPosition] += abs(newPosition - currentBox);
                }
            }
        }
        return answer;
    }
};

GPT

이 코드는 주어진 문자열 boxes에 대해 각 인덱스별로 모든 ‘1’ (공이 있는 위치)로부터 이동하는 데 필요한 연산 횟수를 계산하는 문제를 해결하는 코드입니다.

문제 설명

  • boxes는 ‘0’과 ‘1’로 이루어진 문자열로, 길이는 ( n )입니다.
  • ‘1’은 공이 있는 위치를 나타내며, ‘0’은 공이 없는 위치입니다.
  • 각 인덱스 i에 대해, boxes[i]에 있는 공이 다른 모든 ‘1’에서 이동하는 데 필요한 거리(연산 횟수)를 계산하여 반환합니다.
  • 연산 횟수는 단순히 맨해튼 거리로 계산됩니다. 즉, 한 칸 이동하는 것은 1번 연산입니다.

코드 분석

vector<int> minOperations(string boxes) {
    vector<int> answer(boxes.length()); // 결과를 저장할 벡터 초기화 (모두 0)
  • answer는 각 인덱스에서 공들이 이동하는 데 필요한 총 연산 횟수를 저장할 벡터입니다.
  • 크기는 boxes.length()와 같으며, 모든 값은 0으로 초기화됩니다.
for (int currentBox = 0; currentBox < boxes.length(); currentBox++) {
  • currentBox는 현재 검사 중인 박스의 인덱스를 나타냅니다.
    if (boxes[currentBox] == '1') {
  • 현재 박스에 공(‘1’)이 있을 경우에만 계산을 수행합니다.
        for (int newPosition = 0; newPosition < boxes.length(); newPosition++) {
            answer[newPosition] += abs(newPosition - currentBox);
        }
  • 현재 공이 있는 위치(currentBox)에서 모든 newPosition으로 공을 옮길 때 필요한 이동 횟수를 누적합니다.
  • abs(newPosition - currentBox)를 이용하여 두 인덱스 간의 거리(연산 횟수)를 구합니다.
return answer;
  • 최종적으로 각 박스에 대해 공들이 이동하는 총 연산 횟수가 들어 있는 answer 벡터를 반환합니다.

예제 실행

입력

string boxes = "110";
Solution sol;
vector<int> result = sol.minOperations(boxes);

과정

인덱스boxes[i]0으로 이동 필요1로 이동 필요2로 이동 필요
01012
11101
20210

따라서, 최종적으로 result = [1+2, 0+1, 2+1] = [1, 1, 3]이 됩니다.

출력

[1, 1, 3]

시간 복잡도 분석

이 코드는 이중 루프를 사용합니다:

  • 첫 번째 루프: 모든 currentBox에 대해 실행 (( O(n) ))
  • 두 번째 루프: 각 currentBox에서 모든 newPosition을 탐색 (( O(n) ))

총 시간 복잡도는 O(n2)O(n^2)입니다.

더 효율적인 방법 (O(n) 풀이)

현재 풀이법은O(n2)O(n^2)이지만, 이를 두 번의 선형 탐색으로 줄여 O(n)O(n)에 해결할 수 있습니다.

개선된 접근 방식

  1. 왼쪽에서 오른쪽으로 탐색하며 연산 횟수 누적
    • 왼쪽에 있는 모든 공들을 현재 위치로 이동시키는 데 필요한 연산 횟수를 계산
  2. 오른쪽에서 왼쪽으로 탐색하며 연산 횟수 누적
    • 오른쪽에 있는 모든 공들을 현재 위치로 이동시키는 데 필요한 연산 횟수를 계산

이 방법을 사용하면 한 번의 O(n) 탐색으로 왼쪽에서 이동하는 거리 합을 구하고, 또 한 번의 O(n) 탐색으로 오른쪽에서 이동하는 거리 합을 구할 수 있습니다.
즉, 시간 복잡도는 O(n)O(n)이 됩니다.

개선된 코드 (O(n) 풀이)

class Solution {
public:
    vector<int> minOperations(string boxes) {
        int n = boxes.length();
        vector<int> answer(n, 0);
        int count = 0, operations = 0;

        // 왼쪽에서 오른쪽으로 이동하면서 연산 횟수 누적
        for (int i = 0; i < n; i++) {
            answer[i] = operations;
            count += (boxes[i] == '1') ? 1 : 0;
            operations += count;
        }

        count = 0, operations = 0;

        // 오른쪽에서 왼쪽으로 이동하면서 연산 횟수 추가
        for (int i = n - 1; i >= 0; i--) {
            answer[i] += operations;
            count += (boxes[i] == '1') ? 1 : 0;
            operations += count;
        }

        return answer;
    }
};

시간 복잡도

  • 왼쪽에서 오른쪽으로 한 번 탐색 →\rightarrow O(n)O(n)
  • 오른쪽에서 왼쪽으로 한 번 탐색 →\rightarrow O(n)O(n)
  • 총 O(n)O(n)

출력 결과

위의 예제 "110"에 대해서도 동일한 [1, 1, 3] 결과가 나옵니다.

결론

  • 원래 코드: O(n2)O(n^2) 시간 복잡도로 비효율적
  • 개선된 코드: O(n)O(n)으로 최적화 가능
  • 개선된 방법을 사용하면 큰 입력(예: boxes 길이가 10510^5 이상)에서도 효율적으로 실행 가능

Approach 2: Sum of Left and Right Moves

  • 2ms, 12.18MB
  • Complexity
    • Let nn be the size of the string boxes.
    • Time Complexity: O(n)O(n)
    • Space Complexity: O(1)O(1)
class Solution {
public:
    vector<int> minOperations(string boxes) {
        int n = boxes.size();
        vector<int> answer(n, 0);

        int ballsToLeft = 0, movesToLeft = 0;
        int ballsToRight = 0, movesToRight = 0;

        // Single pass: calculate moves from both left and right
        for (int i = 0; i < n; i++) {
            // Left pass
            answer[i] += movesToLeft;
            ballsToLeft += boxes[i] - '0';
            movesToLeft += ballsToLeft;

            // Right pass
            int j = n - 1 - i;
            answer[j] += movesToRight;
            ballsToRight += boxes[j] - '0';
            movesToRight += ballsToRight;
        }

        return answer;
    }
};

GPT

이 코드는 O(n) 시간 복잡도로 각 상자에 대해 공을 이동하는 데 필요한 최소 연산 횟수를 계산하는 최적화된 방법을 사용합니다.
기본 아이디어는 왼쪽에서 오른쪽, 오른쪽에서 왼쪽으로 한 번씩 탐색하면서 각 위치에서의 연산 횟수를 누적하는 것입니다.

📌 코드 설명

1️⃣ 변수 초기화

int n = boxes.size();
vector<int> answer(n, 0);

int ballsToLeft = 0, movesToLeft = 0;
int ballsToRight = 0, movesToRight = 0;
  • n: boxes의 길이
  • answer: 결과 벡터, 각 인덱스에서 공 이동 최소 연산 횟수를 저장 (초기값은 0)
  • ballsToLeft: 현재까지 왼쪽에 있는 ‘1’의 개수
  • movesToLeft: 왼쪽에 있는 공들이 현재 위치로 이동하는 데 필요한 총 이동 횟수
  • ballsToRight: 현재까지 오른쪽에 있는 ‘1’의 개수
  • movesToRight: 오른쪽에 있는 공들이 현재 위치로 이동하는 데 필요한 총 이동 횟수

2️⃣ 단일 루프에서 왼쪽과 오른쪽 이동 거리 계산

for (int i = 0; i < n; i++) {
    // 왼쪽에서 현재 위치까지의 이동 거리 추가
    answer[i] += movesToLeft;
    ballsToLeft += boxes[i] - '0';  // 현재 위치가 '1'이면 공 개수 증가
    movesToLeft += ballsToLeft;      // 현재 위치를 지나면서 이후 위치들에 영향을 줌

    // 오른쪽에서 현재 위치까지의 이동 거리 추가
    int j = n - 1 - i;
    answer[j] += movesToRight;
    ballsToRight += boxes[j] - '0';  // 현재 위치가 '1'이면 공 개수 증가
    movesToRight += ballsToRight;    // 현재 위치를 지나면서 이후 위치들에 영향을 줌
}

🔹 왼쪽에서 오른쪽으로 탐색 (i 증가)

  • answer[i] += movesToLeft; → 현재 위치까지 공을 이동시키는 비용을 저장
  • ballsToLeft += (boxes[i] - '0'); → 현재 위치가 ‘1’이면 공 개수 증가
  • movesToLeft += ballsToLeft; → 다음 위치로 이동 시킬 때 필요한 연산 횟수 증가

🔹 오른쪽에서 왼쪽으로 탐색 (j 감소)

  • j = n - 1 - i;를 사용하여 i가 증가할 때 j는 반대 방향에서 감소
  • answer[j] += movesToRight; → 현재 위치까지 공을 이동시키는 비용을 저장
  • ballsToRight += (boxes[j] - '0'); → 현재 위치가 ‘1’이면 공 개수 증가
  • movesToRight += ballsToRight; → 다음 위치로 이동 시킬 때 필요한 연산 횟수 증가

📌 예제 실행

예제 입력

string boxes = "110";
Solution sol;
vector<int> result = sol.minOperations(boxes);

각 단계에서 변수 변화

초기 상태

boxes = "110"
answer = [0, 0, 0]
ballsToLeft = 0, movesToLeft = 0
ballsToRight = 0, movesToRight = 0

왼쪽에서 오른쪽으로 탐색

iboxes[i]answer[i] (누적)ballsToLeftmovesToLeft
0’1’011
1’1’123
2’0’325

현재까지의 answer = [0, 1, 3]

오른쪽에서 왼쪽으로 탐색

jboxes[j]answer[j] (누적)ballsToRightmovesToRight
2’0’300
1’1’1+0 = 111
0’1’0+1 = 123

최종적으로 answer = [1, 1, 3]

📌 시간 복잡도 분석

  • 기존 O(n2)O(n^2) 풀이 →\rightarrow 모든 공이 있는 위치에서 다른 모든 위치로 이동 비용을 계산
  • 개선된 풀이 O(n)O(n) →\rightarrow 단일 루프에서 왼쪽과 오른쪽 이동 비용을 동시에 계산

시간 복잡도

✅ 단 한 번의 O(n)O(n) 반복문으로 해결 →\rightarrow O(n)O(n)

공간 복잡도

✅ answer 배열 외에 추가적인 O(1)O(1) 크기의 변수만 사용 →\rightarrow O(n)O(n) (결과 배열 포함)

📌 결론

  • 이전 O(n2)O(n^2) 방식보다 훨씬 효율적
  • 단 한 번의 루프에서 왼쪽과 오른쪽 이동 횟수를 동시에 계산
  • 최적화된 O(n)O(n) 알고리즘으로 크기가 큰 입력에서도 빠르게 동작

🎯 요약 ✅ 한 번의 루프에서 왼쪽과 오른쪽 이동 비용을 동시에 계산하여 O(n)O(n)으로 최적화
✅ 이전의 이중 루프 방식(O(n2)O(n^2))보다 훨씬 빠름
✅ 효율적이고 직관적인 접근 방식