두 정수 start와 end로 표현되는 범위가 주어졌을 때, 이 구간 [start, end] 안에 존재하는 단항 수(Unary Number)의 개수를 구하는 것이 이번 글의 목표입니다.
어떤 수가 단항 수인지 확인하는 방법은 간단합니다. 각 자릿수의 제곱의 합을 구하고, 그 결과에 대해 같은 과정을 반복했을 때 최종적으로 1에 도달하는지 검사하면 됩니다.
예를 들어 숫자 13을 살펴보겠습니다.
1² + 3² = 10 → 1² + 0² = 1
반복 계산의 최종 합이 1이 되므로 13은 단항 수입니다.
입력·출력 예시
예시 1
start=1 end=20
출력:
Count of Unary Numbers in a Range are: 5
해당되는 숫자는 다음과 같습니다.
1, 7, 10, 12, 13
예시 2
start=50 end=100
출력:
Count of Unary Numbers in a Range are: 7
해당되는 숫자는 다음과 같습니다.
59, 63, 67, 74, 75, 78, 89
접근 방법
1부터 9 사이의 한 자리 수 중에서 단항 수는 1과 7뿐입니다. 따라서 두 자리 이상의 수에 대해서는 자릿수 제곱합을 계속 구해 나가다가 결과가 1이 되는지 확인하면 됩니다. 범위 내의 모든 수에 대해 이 과정을 반복 수행하고, 단항 수를 발견할 때마다 카운트를 증가시킵니다.
- 정수 두 개(start, end)를 입력받습니다.
check_unary(int number): 인자로 받은 값이 단항 수이면 true, 아니면 false를 반환합니다.Unary_range(int start, int end): 범위를 인자로 받아 그 구간에 속한 단항 수의 개수를 반환합니다.- count를 0으로 초기화한 뒤, for 루프로 i를 start부터 end까지 증가시키며
check_unary(i)가 true를 반환할 때마다 count를 1씩 늘립니다. check_unary(int number)함수 내부에서는 임시 변수 total을 사용해 자릿수 제곱합을 누적합니다.- number가 1 또는 7이면 true를 반환하고, 그 외 10 미만의 한 자리 수(number / 10 == 0)는 false를 반환합니다.
- while 루프에서 각 자릿수의 제곱합을 계산한 뒤, 그 합을 인자로 하여 check_unary를 재귀적으로 다시 호출합니다.
- 모든 검사가 끝나면 count를 결과로 반환합니다.
C++ 코드 예제
#include <iostream>
using namespace std;
// 숫자가 단항 수인지 판별하는 재귀 함수
bool check_unary(int number){
int total = 0; // 반드시 0으로 초기화
if (number == 1 || number == 7){
return true;
}
else if (number / 10 == 0){
return false;
}
// 자릿수의 제곱합 계산
while (number != 0){
int temp = number % 10;
total += temp * temp;
number /= 10;
}
// 계산된 합에 대해 다시 판별
return check_unary(total);
}
// 범위 내 단항 수의 개수를 세는 함수
int Unary_range(int start, int end){
int count = 0;
for (int i = start; i <= end; i++){
if (check_unary(i)){
count++;
}
}
return count;
}
int main(){
int start = 200, end = 400;
cout << "Count of Unary Numbers in a Range are: " << Unary_range(start, end);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Count of Unary Numbers in a Range are: 31
참고 사항
- total 변수는 반드시 0으로 초기화해야 합니다. 초기화하지 않으면 쓰레기 값(garbage value)이 더해져 잘못된 판별 결과가 나올 수 있습니다.
- 재귀 호출의 결과를 반드시 return 해야 판별 결과가 호출 스택을 따라 전달되어 최종 답에 올바르게 반영됩니다.
시간 복잡도
각 수에 대한 단항 여부 판별은 자릿수 제곱합 계산을 반복하므로 약 O(log n)의 비용이 듭니다. 범위 내 모든 수에 대해 이를 수행하므로 전체 시간 복잡도는 O((end − start + 1) × log n)이며, 재귀 호출 스택을 제외하면 추가 공간은 거의 필요하지 않습니다.