순환 배열(Circular Array)은 첫 번째 요소가 마지막 요소 바로 뒤에 이어지는 것으로 간주하는 배열입니다. 주로 큐(Queue)를 구현할 때 활용되며, 이번 글에서는 이러한 순환 배열 안에서 연속된 1 또는 0의 최대 개수를 구하는 방법을 알아보겠습니다.
문제 이해하기
구체적인 예시를 통해 문제를 살펴보겠습니다.
입력 − Arr[] = { 1,1,0,1,0,1,0,1,1,1 }
출력 − 최대 연속 1의 개수는 5, 최대 연속 0의 개수는 1
설명 − 배열의 인덱스 7부터 9까지 그리고 순환하여 인덱스 0과 1까지 이어지므로, 1이 총 5개 연속됩니다. 반면 0은 연속되지 않고 단 하나만 존재합니다.
입력 − Arr[] = { 0,0,0,1,0 }
출력 − 최대 연속 1의 개수는 1, 최대 연속 0의 개수는 4
설명 − 마지막 인덱스 4의 0과 순환하여 인덱스 0부터 3까지 이어지므로, 0이 총 4개 연속됩니다.
해결 접근 방법
- 0과 1이 무작위로 배치된 배열 Arr[]을 입력으로 받습니다.
- 변수 N은 배열 Arr[]의 크기를 저장합니다.
- bit 변수에는 셀 대상 값인 1 또는 0이 저장됩니다.
- maxConsecutive(int arr[], int n, int bit) 함수는 배열 자체, 배열의 크기, 그리고 0 또는 1의 비트 값을 세 개의 매개변수로 받으며, 해당 비트의 최대 연속 개수를 반환합니다.
- 배열을 순환 형태로 만들기 위해 temp[2*n] 배열을 사용하여 arr[]을 두 번 복사합니다. while() 루프가 두 번 실행되며 arr[]의 내용을 temp에 담습니다.
- 이후 while(temp[k++]==bit) 조건을 통해 연속된 1(또는 0)의 개수를 세고, 그 결과를 변수 count에 저장합니다.
- 현재까지 발견된 최댓값보다 count가 크다면 maxC에 저장합니다.
- 마지막으로 maxC를 최종 결과로 반환합니다.
구현 코드
#include <iostream>
// 최대 연속 개수를 반환하는 함수
int maxConsecutive(int arr[],int n,int bit){
int count=0;
int temp[2*n]={0};
int maxC=0;
int j=0,k=0; // arr[]을 두 번 복사하기 위한 변수
while(j<2){
for(int i=0;i<n;i++){
temp[k++]=arr[i];
}
j++;
}
k=0;
for(int i=0;i<2*n; i++){
count=0;
while(temp[k++]==bit){
++count;
}
if(maxC<count)
maxC=count;
}
return maxC;
}
int main(){
int Arr[]={1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1 };
int N = 12;
int bit=1;
printf("순환 배열 내 최대 연속 1의 개수: %d",maxConsecutive(Arr,N,bit));
bit=0;
printf("
순환 배열 내 최대 연속 0의 개수: %d",maxConsecutive(Arr,N,bit));
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
순환 배열 내 최대 연속 1의 개수: 6 순환 배열 내 최대 연속 0의 개수: 2