C++로 배열에서 연속된 자동형 수(Automorphic Number)의 최대 개수 구하기

이 문제의 목표는 N개의 요소를 가진 배열에서 연속된 자동형 수(Automorphic Number)의 최대 개수를 구하는 것입니다.

자동형 수란?

자동형 수란 그 수를 제곱했을 때, 제곱 결과의 끝자리 숫자가 원래 수와 동일하게 끝나는 수를 말합니다. 예를 들어 5는 5 × 5 = 25이고, 25가 5로 끝나기 때문에 자동형 수입니다.

문제 이해하기

예제를 통해 문제를 살펴보겠습니다.

입력 − arr[] = {5, 3, 625, 6, 8, 1}

출력 − 2

설명 − 위 배열에 존재하는 자동형 수는 5, 625, 6, 1입니다. 하지만 연속적으로 배치된 자동형 수 중 가장 긴 구간은 {625, 6}이므로 출력값은 2가 됩니다.

입력 − arr[] = {33, 25, 1, 76, 4}

출력 − 3

해결 접근 방식

main() 함수에서 int형 변수 'n'을 선언하고, 주어진 배열의 크기를 저장합니다.
MaxAutomorphic() 함수 안에서 현재 연속 구간의 길이를 저장할 CurrentMax와 지금까지 발견한 최댓값을 저장할 Maximum을 모두 int형으로 선언하고 0으로 초기화합니다.
i = 0부터 i < n까지 반복하면서 IsAutomorphic() 함수를 호출하여 해당 요소가 자동형 수인지 검사합니다.
IsAutomorphic() 함수 내부에서는 int형 변수 sqr에 n * n의 값을 저장하여 n의 제곱을 보관합니다.
n > 0인 동안 while 반복문을 사용해 n과 sqr의 마지막 자릿수를 하나씩 비교함으로써 해당 수가 자동형 수인지 판별합니다.
MaxAutomorphic() 함수로 돌아와서, 만약 해당 요소가 자동형 수가 아니라면 CurrentMax를 0으로 초기화합니다.
반대로 자동형 수라면 CurrentMax에 1을 더하고, CurrentMax와 Maximum 중 더 큰 값을 Maximum 변수에 저장합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
// 숫자가 자동형 수인지 확인하는 함수
bool IsAutomorphic(int n){
    // n의 제곱을 저장
    int sqr = n * n;
    // 자릿수 비교
    while (n > 0){
       /* n의 어떤 자릿수라도 제곱값의
       끝자리와 일치하지 않으면 false 반환 */
       if (n % 10 != sqr % 10)
          return false;
       n /= 10;
       sqr /= 10;
    }
    return true;
}
// 연속된 자동형 수의 최대 개수를 구하는 함수
int MaxAutomorphic(int arr[], int size){
    int CurrentMax = 0, Maximum = 0;
    for (int i = 0; i < size; i++){
       // 해당 요소가 자동형 수가 아닌 경우
       if (IsAutomorphic(arr[i]) == false)
          CurrentMax = 0;
       // 자동형 수인 경우 CurrentMax와 Maximum 갱신
       else{
          CurrentMax++;
          Maximum = max(CurrentMax, Maximum);
       }
    }
    return Maximum;
}
// 메인 함수
int main(){
    int arr[] = { 33, 25, 1, 76, 4 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << MaxAutomorphic(arr, size);
    return 0;
}

실행 결과

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