분할정복으로 중복 데이터 개수 찾기

문제

데이터가 정렬 된 배열에서 특정 값의 개수를 찾는 문제였다. 값은 중복될 수 있다.

접근법

• 선형탐색
• 이분탐색

데이터가 정렬되어 있는 형태였기 때문에 선형탐색보다 이분탐색을 하기로 하였다. 그런데 이번 문제의 경우 데이터의 중복이 존재하는 경우였다. 따라서 이분탐색으로 값의 위치를 찾되, 찾은 위치를 기준으로 값이 존재하는 위치 구간을 찾기로 하였다.

구현

값의 위치 찾기

이분탐색을 적용한다.

int binarySearch(const vector<int> &arr, int x) {
    int left = 0;
    int right = arr.size();
    int check = -1;
    while (left <= right) {

        int mid = (left + right) / 2;
        int search = arr[mid];

        if (search < x) {
            left = mid + 1;
        } else if (search > x) {
            right = mid - 1;
        } else if (arr[mid] == x) {
            check = mid;
            break;
        }
    }
    return check;
}

값의 구간 찾기

찾은 위치를 기준으로 이분탐색 로직을 사용한다. 영역은 값의 위치를 기준으로 왼쪽 영역과 오른쪽 영역을 아눈다.

int Count3(const vector<int> &arr, int x) {
    int check = binarySearch(arr, x);
    if (check == -1) {
        return 0;
    }

    int l = check;
    int r = check;

    int left = 0;
    int right = arr.size();

        // 왼쪽 영역
    while (l - left > 1) {
        int m = (left + l) / 2;
        int c = arr[m];
        if (c != x) {
            left = m;
        } else {
            l = m;
        }
    }

        // 오른쪽 영역
    while (right - r > 1) {
        int m = (right + r) / 2;
        int c = arr[m];
        if (c != x) {
            right = m;
        } else {
            r = m;
        }
    }

    return r - l + 1;
}

왼쪽 영역을 기준으로 설명을 할 때 좌측 포인터와 우측 포인터의 중간 인덱스를 계산해서 그 위치의 값이 찾으려고 하는 값과 동일하다면 우측 포인터를 중간 인덱스로 옮기고 그 반대면 좌측 포인터를 중간 인덱스로 옮긴다. 좌측포인터와 우측 포인터의 차이가 1이 날때까지 반복한다.

    int l = check;
    int left = 0;

        // 왼쪽 영역
    while (l - left > 1) {
        int m = (left + l) / 2;
        int c = arr[m];
        if (c != x) {
            left = m;
        } else {
            l = m;
        }
    }

반복이 끝난 후에 값이 존재하는 포인터를 반환한다. 오른쪽 영역도 같은 논리로 경계를 찾고 값이 존재하는 포인터를 반환한다.

    int r = check;
    int right = arr.size();

        // 오른쪽 영역
    while (right - r > 1) {
        int m = (right + r) / 2;
        int c = arr[m];
        if (c != x) {
            right = m;
        } else {
            r = m;
        }
    }

두 포인터의 차에 1을 더하면 값이 존재하는 구간에서 값의 개수를 구할 수 있다.

    return r - l + 1;

회고

이분탐색은 분할정복법을 적용한 알고리즘이다. 분할정복법을 사용하면 문제를 푸는 데에 필요한 시간을 줄일 수 있다. 값이 중복 될 경우에 값의 개수를 찾는 문제도 분할정복을 활용한 문제다. 배열 전체를 탐색하는 대신에 데이터가 정렬되어 있다는 특성을 이용하여 경계를 찾으려고 했다.

데이터가 정렬되어 있고 중복데이터의 개수를 찾아야한다면 이분탐색과 이를 응용한 알고리즘을 작성하는 방법을 찾게 되었다.