C++로 배열의 주어진 범위에서 인접한 동일 요소 개수 세는 방법

배열과 인덱스 범위가 주어졌을 때, 해당 범위 안에서 서로 인접하면서 값이 같은 요소가 몇 개 있는지 세는 문제입니다. 이 문제는 단순 반복문 하나로 효율적으로 해결할 수 있습니다.

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

예시

입력

arr = [1, 2, 2, 2, 3, 3, 4]
lower = 1
upper = 5

출력

인덱스 1부터 5 사이에서 인접한 요소들을 비교하면, (2, 2), (2, 2), (3, 3)으로 총 3쌍이 같은 값을 가지므로 결과는 3이 됩니다.

알고리즘

배열과 탐색할 인덱스 범위(lower, upper)를 초기화합니다.
lower 인덱스부터 upper - 1 인덱스까지 순회하는 반복문을 작성합니다.
- 현재 요소와 다음 요소를 비교합니다.
- 두 요소가 같다면 카운트를 1 증가시킵니다.
순회가 끝나면 카운트를 반환합니다.

C++ 구현

다음은 위 알고리즘을 C++로 구현한 코드입니다.

#include <bits/stdc++.h>
using namespace std;

int getEqualElementsCount(int arr[], int n, int lower, int upper) {
    int count = 0;
    for (int i = lower; i < upper; i++) {
        if (arr[i] == arr[i + 1]) {
            count += 1;
        }
    }
    return count;
}

int main() {
    int arr[] = { 1, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5 };
    int n = 15;
    cout << getEqualElementsCount(arr, n, 1, n - 1) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

시간 복잡도 분석

이 알고리즘은 범위 내 각 인덱스를 한 번씩만 방문하므로 시간 복잡도는 O(upper - lower)이며, 추가 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다. 매우 단순하지만 선형 시간에 해결되는 효율적인 접근 방식입니다.