문제 소개
n대의 슈퍼 세탁기가 한 줄로 나열되어 있다고 가정해 봅시다. 처음 상태에서 각 세탁기에는 옷이 몇 벌씩 들어 있거나 비어 있을 수 있습니다. 매 이동(move)마다 임의의 m개(1 ≤ m ≤ n)의 세탁기를 선택할 수 있으며, 선택된 각 세탁기는 자신이 가진 옷 한 벌을 인접한 세탁기 중 하나로 동시에 전달합니다.
왼쪽부터 오른쪽까지 각 세탁기에 들어 있는 옷의 개수를 담은 정수 배열이 주어질 때, 모든 세탁기의 옷 개수를 동일하게 만들기 위해 필요한 최소 이동 횟수를 구하는 것이 목표입니다. 만약 균등하게 분배하는 것이 불가능하다면 -1을 반환해야 합니다.
예시로 이해하기
입력이 [1, 0, 5]인 경우 출력은 3입니다.
- 첫 번째 이동: 마지막 세탁기의 5 중 1벌을 가운데로 →
[1, 1, 4] - 두 번째 이동: 가운데의 1을 왼쪽으로, 오른쪽의 4에서 1벌을 가운데로 →
[2, 1, 3] - 세 번째 이동: 왼쪽의 2에서 1벌을 가운데로 →
[2, 2, 2]
이렇게 총 3번의 이동으로 모든 세탁기의 옷 개수를 2개로 맞출 수 있습니다.
해결 알고리즘
이 문제는 누적 불균형(cumulative balance)을 활용한 그리디 방식으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 전체 옷의 합(sum)을 구하고, 세탁기 대수(n)로 나누어 떨어지지 않으면 균등 분배가 불가능하므로 -1을 반환합니다.
- 각 세탁기가 가져야 할 목표치(req = sum / n)를 계산합니다.
- 왼쪽부터 순회하면서 현재 위치까지의 누적 초과분(extra)을 추적합니다. extra 값은 특정 경계를 기준으로 좌우 간에 반드시 넘겨야 하는 옷의 양을 의미합니다.
- 정답(ret)은 다음 세 값 중 최댓값으로 갱신됩니다.
- 현재까지의 정답 ret
- 현재 세탁기의 초과분 (x - req): 한 세탁기가 인접 세탁기로 내보내야 하는 최소 이동량
- 누적 초과분의 절댓값 |extra|: 경계를 넘어 흘러야 하는 옷의 양
매 이동마다 여러 세탁기가 동시에 옷을 전달할 수 있으므로, 위 세 값 중 가장 큰 값이 곧 필요한 최소 이동 횟수가 됩니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findMinMoves(vector<int>& v) {
int sum = accumulate(v.begin(), v.end(), 0);
int n = v.size();
if(sum % n != 0) return -1;
int req = sum / n;
int ret = 0;
int extra = 0;
for(int i = 0; i < n; i++){
int x = v[i];
extra += (x - req);
ret = max({ret, x - req, abs(extra)});
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {2,1,6};
cout << (ob.findMinMoves(v));
}입력
{2, 1, 6}출력
3
복잡도 분석
- 시간 복잡도: O(n) — 배열을 한 번만 순회합니다.
- 공간 복잡도: O(1) — 추가 배열 없이 몇 개의 변수만 사용합니다.
이처럼 누적합과 그리디 기법을 결합하면 세탁기 배분 문제를 선형 시간 안에 효율적으로 해결할 수 있습니다.