이 튜토리얼에서는 C++을 사용해 주어진 숫자가 키스 수(Keith Number)인지 아닌지 판별하는 프로그램을 작성해 보겠습니다.
키스 수란 무엇인가?
어떤 수 n의 자릿수들로 수열을 만들었을 때, 그 수열 안에 n 자신이 다시 나타난다면 n을 키스 수라고 부릅니다. 이 수열은 다음과 같은 규칙으로 생성됩니다.
- 수열의 첫 항들은 숫자 n의 각 자릿수입니다.
- 이후의 항들은 앞선 n개 항(자릿수 개수만큼)의 합으로 재귀적으로 계산됩니다.
예를 들어 14를 살펴보겠습니다. 자릿수는 1과 4이므로 수열은 다음과 같이 진행됩니다.
1 → 4 → (1+4)=5 → (4+5)=9 → (5+9)=14
수열에 14가 다시 등장하므로 14는 키스 수입니다. 대표적인 키스 수로는 14, 19, 28, 47, 61, 75, 197, 742 등이 있습니다.
문제 해결 접근 방법
키스 수를 판별하는 과정은 다음 단계로 진행할 수 있습니다.
- 판별할 숫자 n을 초기화합니다.
- 수열을 저장할 빈 벡터 elements를 준비합니다.
- n의 자릿수 개수를 세고, 각 자릿수를 벡터에 추가합니다.
- 자릿수 벡터를 뒤집어 원래 순서대로 정렬합니다.
- 다음 항을 저장할 변수 nextElement를 0으로 초기화합니다.
- nextElement가 n보다 작은 동안 반복하는 루프를 작성합니다.
- 벡터의 마지막 n개 항을 모두 더해 nextElement를 계산합니다.
- 계산된 nextElement를 벡터에 추가합니다.
- 루프가 끝난 후 nextElement가 n과 같으면 true, 그렇지 않으면 false를 반환합니다.
예제 코드
위 알고리즘을 C++ 코드로 구현하면 다음과 같습니다.
#include<bits/stdc++.h>
using namespace std;
bool isKeithNumber(int n) {
vector<int> elements;
int temp = n, digitsCount = 0;
while (temp > 0) {
elements.push_back(temp % 10);
temp = temp / 10;
digitsCount++;
}
reverse(elements.begin(), elements.end());
int nextElement = 0, i = digitsCount;
while (nextElement < n) {
nextElement = 0;
for (int j = 1; j <= digitsCount; j++) {
nextElement += elements[i - j];
}
elements.push_back(nextElement);
i++;
}
return nextElement == n;
}
int main() {
isKeithNumber(43) ? cout << "Yes" << endl : cout << "No" << endl;
isKeithNumber(14) ? cout << "Yes" << endl : cout << "No" << endl;
isKeithNumber(197) ? cout << "Yes" << endl : cout << "No" << endl;
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
No Yes Yes
43은 키스 수가 아니므로 No가 출력되고, 14와 197은 키스 수이므로 Yes가 출력되는 것을 확인할 수 있습니다.
마무리
이번 튜토리얼에서는 자릿수 기반 수열을 활용해 키스 수를 판별하는 방법을 배웠습니다. 시간 복잡도는 수열이 n에 도달할 때까지 확장되기 때문에 입력 값의 크기에 따라 달라지지만, 일반적인 범위에서는 충분히 효율적으로 동작합니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.