길이가 n인 연속된 숫자 배열이 주어졌을 때, 배열에는 단 하나의 숫자만 두 번 이상 반복되어 나타납니다. 이때 우리의 목표는 해당 요소가 배열에서 몇 번 반복되는지 그 횟수를 구하는 것입니다. 다시 말해, 반복되는 요소의 길이를 찾는 문제라고 할 수 있습니다.
해결 방법은 간단합니다. 인덱스 i=0부터 i<n까지 배열을 순회하면서 arr[i]==arr[i+1] 조건을 만족하면 count를 1씩 증가시킵니다. 마지막으로 마지막 요소까지 포함하기 위해 count를 한 번 더 증가시키면, count 변수에는 반복 요소의 길이가 저장됩니다.
예제로 이해하기
예제 1
- 입력 − arr[] = { 0, 1, 2, 3, 3, 3 }, N = 6
- 출력 − 반복 요소의 개수: 3
- 설명 − 숫자 3이 세 번 반복됩니다.
예제 2
- 입력 − arr[] = { 1, 2, 3, 4, 4, 4, 4, 4, 5, 6 }, N = 10
- 출력 − 반복 요소의 개수: 5
- 설명 − 숫자 4가 다섯 번 반복됩니다.
프로그램의 접근 방식
- 연속된 숫자로 초기화된 정수 배열 arr[]을 준비합니다. 이 배열에서 하나의 숫자만 반복됩니다.
- 변수 len은 배열의 길이를 저장합니다.
- 함수 findRepeat(int arr[], int n)는 배열과 그 길이를 입력으로 받아, 반복되는 요소의 값과 반복 횟수를 출력합니다.
- 초기 count 값을 0으로 설정합니다.
- 인덱스 i=0부터 i<n까지 순회하면서 arr[i]==arr[i+1]이면 count를 증가시키고, 해당 요소를 value 변수에 저장합니다.
- 루프가 끝나면 마지막 요소를 포함하기 위해 count를 1 증가시킵니다.
- 반복되는 요소를 value로 출력합니다.
- 반복 횟수를 count로 출력합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
void findRepeat(int arr[],int n){
int count=0; //count of repeated element
int value=0; //to store repeated element
for(int i=0;i<n;i++){
if(arr[i]==arr[i+1]){
count++;
value=arr[i];
}
}
count++; //for last element
cout<<"Repeated Element: "<<value;
cout<<endl<<"Number of occurrences: "<<count;
}
int main(){
int Arr[]={ 2,3,4,5,5,5,6,7,8 };
int len=sizeof(Arr)/sizeof(Arr[0]);
findRepeat(Arr,len);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Repeated Element: 5 Number of occurrences: 3
이 알고리즘은 배열이 이미 정렬되어 있고 반복 요소가 하나뿐이라는 전제 조건 덕분에 시간 복잡도 O(n)으로 선형 탐색만으로 문제를 해결할 수 있습니다. 배열이 정렬되어 있지 않다면 먼저 정렬을 수행한 뒤 동일한 방식을 적용할 수 있습니다.