이 문제에서는 0 또는 1로 이루어진 n개의 요소를 가진 배열 arr가 주어집니다. 우리의 목표는 이웃을 채우는 연산을 최소한의 반복 횟수만 사용하여 배열 전체를 1로 채우는 것입니다.
문제 이해를 위한 예시
입력: arr[] = {0, 1, 1, 0, 0, 1}
출력: 1
배열에 이미 존재하는 1들이 인접한 0들을 변환하는 데 필요한 최소 반복 횟수는 1입니다.
해결 접근 방식
이 문제를 해결하려면 한 가지 핵심 사실을 먼저 알아야 합니다. 바로 특정 위치에 1이 존재하면, 그 양옆에 있는 두 개의 0을 1로 변환할 수 있다는 점입니다.
- 만약 arr[i]가 1이라면,
- 그 다음 반복에서 arr[i-1]과 arr[i+1]이 1로 변환됩니다.
이 성질을 활용하면 0으로 이루어진 연속 구간(블록)의 위치에 따라 다음 세 가지 경우 중 하나로 답을 계산할 수 있습니다.
경우 1: 블록의 시작과 끝 양쪽에 1이 있는 경우
블록 내부의 나머지 값은 모두 0입니다. 이때 0의 개수(zeroCount)를 세어 아래와 같이 계산합니다.
- 반복 횟수 = zeroCount / 2 (개수가 짝수일 때)
- 반복 횟수 = (zeroCount + 1) / 2 (개수가 홀수일 때)
즉, 양쪽의 1이 서로를 향해 번져가며 채워나가므로 반복 횟수는 zeroCount를 올림하여 2로 나눈 값이 됩니다.
경우 2: 블록의 시작 또는 끝 중 한쪽에만 1이 있는 경우
배열의 경계에 붙은 0 구간처럼 한쪽에서만 1이 번져나갈 수 있는 경우입니다.
- 반복 횟수 = zeroCount
경우 3: 블록에 1이 전혀 없는 경우
배열 전체에 1이 하나도 없다면 1을 만들 수 없으므로, -1을 반환하여 1로 채우는 것이 불가능함을 나타냅니다.
솔루션 동작 예제 프로그램
#include<iostream>
using namespace std;
int countIterationFill1(int arr[], int n) {
bool oneFound = false;
int iterationCount = 0;
for (int i=0; i<n; ) {
if (arr[i] == 1)
oneFound = true;
while (i<n && arr[i]==1)
i++;
int zeroCount = 0;
while (i<n && arr[i]==0) {
zeroCount++;
i++;
}
if (oneFound == false && i == n)
return -1;
int itrCount;
if (i < n && oneFound == true) {
if (zeroCount % 2 == 0)
itrCount = zeroCount/2;
else
itrCount = (zeroCount+1)/2;
zeroCount = 0;
}
else{
itrCount = zeroCount;
zeroCount = 0;
}
iterationCount = max(iterationCount, itrCount);
}
return iterationCount;
}
int main() {
int arr[] = {0, 1, 1, 0, 0, 1, 0, 0, 0, 1};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The number of iterations to fill 1's is "<<countIterationFill1(arr, n);
return 0;
}
출력 결과
The number of iterations to fill 1's is 2
동작 원리 설명
위 프로그램은 배열을 한 번 순회하면서 연속된 0의 구간을 찾아내고, 각 구간이 어느 경우에 해당하는지 판단하여 필요한 반복 횟수를 계산합니다. 각 구간의 반복 횟수 중 가장 큰 값이 곧 전체 배열을 1로 채우는 데 필요한 최소 반복 횟수가 됩니다.
예제 입력 {0, 1, 1, 0, 0, 1, 0, 0, 0, 1}의 경우를 살펴보면 다음과 같습니다.
- 맨 앞의 0 한 개(경계 구간): 1번의 반복 필요
- 두 1 사이의 0 두 개({0, 0}): 2 / 2 = 1번의 반복 필요
- 두 1 사이의 0 세 개({0, 0, 0}): (3 + 1) / 2 = 2번의 반복 필요
따라서 최대값인 2가 정답으로 출력됩니다. 이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리 사용 없이 O(1)의 공간 복잡도로 해결할 수 있다는 장점이 있습니다.