C++로 배열의 모든 요소를 0으로 만들기 위한 최소 연산 횟수 구하기

문제 설명

크기가 N인 배열이 주어지며, 배열의 각 요소는 1 또는 0입니다. 이 문제의 목표는 모든 요소를 0으로 만들기 위해 수행해야 하는 최소 연산 횟수를 구하는 것입니다.

수행할 수 있는 연산은 다음과 같습니다. 어떤 요소가 1이라면, 그 값을 0으로 변경할 수 있습니다. 이때 다음 규칙이 적용됩니다.

바로 다음에 오는 연속된 요소가 1이면, 해당 요소도 자동으로 0으로 변환됩니다.
바로 다음에 오는 연속된 요소가 이미 0이라면, 아무런 변화도 일어나지 않습니다.

예를 들어, 다음 배열을 살펴보겠습니다.

arr[] = {1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1}
→ 모든 요소를 0으로 만들려면 4번의 연산이 필요합니다.

핵심 아이디어와 알고리즘

이 문제의 핵심은 연속된 1의 묶음(그룹)을 파악하는 것입니다. 하나의 연산으로 값이 1인 요소를 0으로 바꾸면, 그 뒤에 이어진 연속된 1들이 모두 한 번에 0으로 바뀌기 때문입니다. 따라서 최소 연산 횟수는 배열에서 1이 연속해서 나타나는 그룹의 개수와 같습니다.

1. 현재 요소가 1이면 카운트(cnt)를 1 증가시키고,
   연속된 1들은 자동으로 0으로 변환되므로 다음 0이 나오는 위치까지 건너뜁니다.
2. 배열 전체를 순회한 후, 최종 카운트를 반환합니다.

시간 복잡도: O(N)
공간 복잡도: O(1)

예제 코드

#include <iostream>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int performMinOperation(int *arr, int n){
    int i, cnt = 0;
    for (i = 0; i < n; ++i) {
        if (arr[i] == 1) {
            int j;
            for (j = i + 1; j < n; ++j) {
                if (arr[j] == 0) {
                    break;
                }
            }
            i = j - 1;
            ++cnt;
        }
    }
    return cnt;
}
int main(){
    int arr[] = {1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1};
    cout << "Minimum required operations = " << performMinOperation(arr, SIZE(arr)) << endl;
    return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

Minimum required operations = 4

동작 원리 살펴보기

주어진 배열 {1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1}에는 1이 연속된 그룹이 총 세 곳 존재합니다. 인덱스 0~1의 {1, 1}, 인덱스 4~8의 {1, 1, 1, 1, 1}, 그리고 마지막 인덱스 14의 {1}이 바로 그 그룹입니다. 세 번의 연산으로 이 세 그룹이 모두 0이 되지만, 마지막 단일 1 그룹까지 처리하면 총 4번의 연산이 필요하게 됩니다. 즉, 이 알고리즘은 배열을 한 번만 순회하면서 1의 그룹 시작 지점을 만날 때마다 카운트를 증가시키는 방식으로 정답을 효율적으로 구할 수 있습니다.