이 글에서는 양의 정수로 이루어진 배열이 주어졌을 때, 배열 안에 존재하는 최장 연속 숫자(연속된 수열)의 개수를 구하는 방법을 다룹니다.
핵심 아이디어는 간단합니다. 먼저 배열을 오름차순으로 정렬한 뒤, 인접한 두 원소를 비교하며 arr[j] == arr[i] + 1 (j = i + 1) 조건을 검사합니다. 두 값의 차이가 1이라면 연속 숫자이므로 카운트를 증가시키고 인덱스 i와 j를 각각 하나씩 앞으로 이동시킵니다. 차이가 1이 아니라면 연속이 끊긴 것이므로 카운트를 1로 초기화합니다. 이 과정에서 지금까지 발견한 최대 카운트를 변수 maxc에 저장해 두고, 최종적으로 maxc를 결과로 반환합니다.
입력 / 출력 예제 1
Arr[] = { 100, 21, 24, 73, 22, 23 }출력:
배열 내 최대 연속 숫자 개수 : 4
설명 − 정렬된 배열은 { 21, 22, 23, 24, 73, 100 }이며, 초기값은 count = 1, maxcount = 1입니다.
1. 22 = 21 + 1 → count=2, maxcount=2, i++, j++ 2. 23 = 22 + 1 → count=3, maxcount=3, i++, j++ 3. 24 = 23 + 1 → count=4, maxcount=4, i++, j++ 4. 73 ≠ 24 + 1 → count=1, maxcount=4, i++, j++ 5. 100 ≠ 73 + 1 → count=1, maxcount=4, i++, j++
따라서 최대 연속 숫자는 4개 { 21, 22, 23, 24 }입니다.
입력 / 출력 예제 2
Arr[] = { 11, 41, 21, 42, 61, 43, 9, 44 }출력:
배열 내 최대 연속 숫자 개수 : 4
설명 − 정렬된 배열은 { 9, 11, 21, 41, 42, 43, 44, 61 }이며, 초기값은 count = 1, maxcount = 1입니다.
1. 11 ≠ 9 + 1 → count=1, maxcount=1, i++, j++ 2. 21 ≠ 11 + 1 → count=1, maxcount=1, i++, j++ 3. 41 ≠ 21 + 1 → count=1, maxcount=1, i++, j++ 4. 42 = 41 + 1 → count=2, maxcount=2, i++, j++ 5. 43 = 42 + 1 → count=3, maxcount=3, i++, j++ 6. 44 = 43 + 1 → count=4, maxcount=4, i++, j++ 7. 61 ≠ 44 + 1 → count=1, maxcount=4, i++, j++
따라서 최대 연속 숫자는 4개 { 41, 42, 43, 44 }입니다.
알고리즘 접근 방식
정수 배열 Arr[]에 정수들을 저장합니다.
정수 n에는 배열의 길이를 저장합니다.
함수 subs(int arr[], int n)는 배열과 그 크기를 입력받아, 배열에 존재하는 최대 연속 숫자의 개수를 반환합니다.
먼저 sort(arr, arr + n)을 사용해 배열을 오름차순으로 정렬합니다.
count = 1과 maxc = 1로 초기화합니다.
첫 번째 두 원소 arr[0], arr[1]부터 시작하여 이중 for문 안에서 arr[j] == arr[i] + 1 (j = i + 1) 조건을 검사하고, 참이면 count와 i를 1씩 증가시킵니다.
조건이 거짓이면 count를 다시 1로 되돌립니다. 매 반복마다 지금까지의 최댓값을 갱신합니다(maxc = count > maxc ? count : maxc).
마지막에 maxc를 최대 연속 원소의 개수로 반환합니다.
C++ 구현 예제
#include <iostream>
#include <algorithm>
using namespace std;
int subs(int arr[], int n){
std::sort(arr, arr + n);
int count = 1;
int maxc = 1;
for(int i = 0; i < n - 1; i++){
for(int j = i + 1; j < n; j++){
if(arr[j] == arr[i] + 1){
count++;
i++;
}
else
count = 1;
maxc = count > maxc ? count : maxc;
}
}
return maxc;
}
int main(){
int arr[] = { 10, 9, 8, 7, 3, 2, 1, 4, 5, 6 };
int n = sizeof(arr) / sizeof(int);
cout << "배열에 존재하는 최대 연속 숫자 개수 : " << subs(arr, n);
return 0;
}출력 결과
배열에 존재하는 최대 연속 숫자 개수 : 10
위 예제에서 입력 배열 { 10, 9, 8, 7, 3, 2, 1, 4, 5, 6 }을 정렬하면 { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }이 되므로, 전체 배열이 하나의 연속 수열을 이루어 결과는 10이 됩니다.