C++로 정렬된 이진 배열에서 0의 개수 찾기

이 문제에서는 0과 1로만 구성된 이진 배열 bin[]이 주어지며, 우리의 목표는 배열에 포함된 0의 개수를 찾는 것입니다.

배열은 정렬되어 있어서 모든 0이 1 뒤에 함께 배치되어 있습니다.

예시를 통해 문제를 이해해 보겠습니다.

입력

arr[] = {1, 1, 1, 0, 0, 0, 0}

출력

4

문제 해결 접근법

이 문제의 핵심 아이디어는 배열이 정렬되어 있다는 특성을 활용하는 것입니다. 배열에서 처음으로 0이 등장하는 위치만 찾으면, 그 이후의 모든 값이 0이므로 '배열의 전체 크기 − 첫 번째 0의 인덱스'로 0의 개수를 바로 구할 수 있습니다.

첫 번째 0의 위치를 찾기 위해 다음 두 가지 탐색 알고리즘을 사용할 수 있습니다.

1. 선형 탐색 (Linear Search)

선형 탐색은 배열을 처음부터 끝까지 순회하면서 처음으로 0을 만나는 순간 해당 인덱스를 반환하는 방식입니다. 이 방법은 구현이 간단하지만 시간 복잡도가 O(N)이라는 점이 단점입니다.

예제 1: 선형 탐색

아래 프로그램은 선형 탐색 기반 솔루션의 동작을 보여줍니다.

#include <iostream>
using namespace std;

int findFirstZero(int arr[], int n){
    for(int i = 0; i < n; i++){
        if(arr[i] == 0){
            return i;
        }
    }
    return -1;
}

int countZerosArr(int arr[], int n){
    int firstOccZero = findFirstZero(arr, n);
    if (firstOccZero == -1)
        return 0;
    return (n - firstOccZero);
}

int main(){
    int arr[] = {1, 1, 1, 1, 0, 0, 0, 0, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"배열에 있는 0의 개수: "<<countZerosArr(arr, n);
    return 0;
}

출력

배열에 있는 0의 개수: 5

2. 이진 탐색 (Binary Search)

이진 탐색은 중간(mid) 위치의 값이 1인지 0인지에 따라 탐색 범위를 절반씩 줄여가며 첫 번째 0의 인덱스를 찾습니다. 정렬된 배열의 장점을 극대화하는 방법으로, 시간 복잡도는 O(log N)으로 선형 탐색보다 훨씬 효율적입니다.

예제 2: 이진 탐색

아래 프로그램은 이진 탐색 기반 솔루션의 동작을 보여줍니다.

#include <iostream>
using namespace std;

int findFirstZero(int arr[], int start, int end){
    if (end >= start){
        int mid = start + (end - start) / 2;
        if ((mid == 0 || arr[mid - 1] == 1) && arr[mid] == 0)
            return mid;
        if (arr[mid] == 1)
            return findFirstZero(arr, (mid + 1), end);
        else
            return findFirstZero(arr, start, (mid - 1));
    }
    return -1;
}

int countZerosArr(int arr[], int n){
    int firstOccZero = findFirstZero(arr, 0, n - 1);
    if (firstOccZero == -1)
        return 0;
    return (n - firstOccZero);
}

int main(){
    int arr[] = {1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"배열에 있는 0의 개수: "<<countZerosArr(arr, n);
    return 0;
}

출력

배열에 있는 0의 개수: 7

마무리

두 방식 모두 '첫 번째 0의 위치'를 찾는다는 동일한 원리를 사용하지만, 배열이 정렬되어 있다는 조건이 주어진다면 이진 탐색(O(log N))이 선형 탐색(O(N))보다 성능 면에서 유리합니다. 따라서 실전에서는 데이터 크기가 클수록 이진 탐색 기반 접근법을 선택하는 것이 좋습니다.