C++에는 수학적 문제를 해결하는 데 활용할 수 있는 다양한 기능들이 있습니다. 그중 하나가 코드를 통해 홀수 자릿수로만 이루어진 N번째 숫자를 찾는 것입니다. 이 글에서는 홀수 자릿수로만 구성된 N번째 숫자를 찾는 전체 과정을 설명하고, 홀수의 개념과 어떤 숫자들이 홀수 자릿수로만 이루어지는지 자세히 살펴보겠습니다.
홀수 자릿수로만 이루어진 N번째 숫자 찾기
홀수는 2로 나누었을 때 나머지가 발생하는 수입니다. 처음 몇 가지 예를 들면 1, 3, 5, 7, 9, 11, 13, 15, 17, 19...와 같습니다.
원하는 숫자를 찾기 위한 두 가지 접근 방법이 있습니다.
접근 방법 1 − 모든 자연수를 하나씩 검사하여 해당 숫자가 홀수인지 확인하고, 홀수를 만날 때마다 카운트를 증가시킵니다. 짝수는 건너뛰고, 카운트가 n과 같아지는 시점의 숫자가 바로 원하는 N번째 숫자입니다.
이 방법은 모든 숫자를 검사하며 홀수의 개수를 세기만 하면 되므로 이해하기 매우 간단하지만, 컴퓨터 프로그래밍 관점에서 보면 이 작업을 완료하는 데 상당히 많은 시간이 걸린다는 단점이 있습니다.
접근 방법 2 − 홀수 자릿수로만 이루어진 모든 숫자는 마지막 자리가 반드시 1, 3, 5, 7, 9 중 하나이므로 자연스럽게 홀수가 됩니다. 따라서 먼저 N번째 숫자가 1, 3, 5, 7, 9 중에 있는지 확인하고, 있다면 곧바로 답을 얻을 수 있습니다. 없다면 다음 후보 숫자들인 11, 13, 15, 17, 19로 넘어가고, 이후에는 21, 23, 25, 27, 29 순으로 진행합니다. 이는 '기존 숫자 × 10 + {마지막 자리 후보 숫자}'라는 규칙적인 패턴으로 표현할 수 있습니다.
예제
마지막 자리 후보 숫자는 1, 3, 5, 7, 9입니다. 다음 가능한 숫자들은 아래와 같이 구할 수 있습니다. 1 * 10 + 1 = 11 1 * 10 + 3 = 13 1 * 10 + 5 = 15 1 * 10 + 7 = 17 1 * 10 + 9 = 19 즉, 11, 13, 15, 17, 19
예제 코드
먼저 전체 코드가 어떤 형태인지 살펴보겠습니다.
#include<bits/stdc++.h>
using namespace std;
int main(){
queue<int> q;
int cnt = 0, ans = 0;
int n;
cin >> n;
int a[5]={1,3,5,7,9};
for(int i = 0; i < 5;i++){
cnt++;
if(cnt == n)
ans = a[i];
q.push(a[i]);
}
if(ans)
cout << ans << "\n";
else{
while(true){
int x = q.front();
q.pop();
for(int j = 0; j < 5; j++) {
int temp = x * 10 + a[j];
q.push(temp);
cnt++;
if(cnt == n)
ans = temp;
}
if(ans)
break;
}
cout << ans << "\n";
}
return 0;
}출력 결과
9
(입력으로 5를 제공하면 출력으로 9를 얻습니다)
위 코드는 홀수 자릿수로만 이루어진 N번째 숫자를 찾는 C++ 코드입니다. 코드를 더 잘 이해하기 위해 각 부분으로 나누어 하나씩 자세히 살펴보겠습니다.
코드 설명
1단계 − 사용자로부터 n을 입력받고 필요한 변수들을 초기화합니다.
int main() {
queue<int> q;
int cnt = 0, ans = 0;
int n;
cin >> n;
int a[5]={1,3,5,7,9};여기서 큐(queue)를 생성하고, 개수를 세는 변수 cnt와 정답을 저장할 변수 ans를 초기화합니다. 또한 cin을 사용해 사용자로부터 입력을 받고, 가장 첫 번째 후보 숫자들로 배열을 초기화합니다.
2단계 − N번째 숫자가 초기 후보 숫자들 안에서 발견되는지 확인하고, 해당 숫자들을 큐에 저장합니다.
for(int i = 0; i < 5; i++){
cnt++;
if(cnt == n)
ans = a[i];
q.push(a[i]);
}
if(ans)
cout << ans << "\n";위 코드에서는 N번째 숫자가 배열에 저장된 초기 후보 숫자들 중에 있는지 확인하고, 배열에 있는 숫자들을 차례대로 큐에 삽입합니다. 만약 N번째 숫자가 초기 후보 숫자들에서 발견되면 즉시 결과를 출력합니다.
3단계 − N번째 숫자를 찾지 못했다면, 다음 후보 숫자들을 생성하며 탐색을 계속합니다.
while(true) {
int x = q.front();
q.pop();
for(int j = 0; j < 5; j++) {
int temp = x * 10 + a[j];
q.push(temp);
cnt++;
if(cnt == n)
ans = temp;
}
if(ans)
break;
}
cout << ans << "\n";마지막으로 큐에서 숫자를 하나씩 꺼내면서 '{x × 10 + 마지막 자리 홀수}' 공식을 사용해 다음 후보 숫자를 생성하고, cnt 값이 n과 같아졌는지 확인합니다. 조건이 충족되면 반복문을 종료하고 결과를 출력합니다.
결론
이 글에서는 홀수 자릿수만으로 이루어진 N번째 숫자를 찾는 문제를 다루었으며, 이를 해결하는 두 가지 접근 방법을 살펴보았습니다. 첫 번째 방법은 단순히 각 숫자를 검사하고 짝수를 건너뛰는 방식이라 이해하기 쉽지만, 연산에 많은 시간이 소요된다는 단점이 있었습니다.
두 번째 방법은 큐를 활용해 홀수 자릿수 숫자들을 저장하고, 앞서 소개한 공식을 이용해 다음 후보 숫자들을 효율적으로 생성하는 방식입니다. 이 방법의 시간 복잡도는 O(n)으로 훨씬 효율적입니다.
이처럼 우리는 C++로 홀수 자릿수만으로 이루어진 N번째 숫자를 찾는 프로그램을 만들었습니다. 같은 로직은 C, Python, Java 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 글이 문제 해결 접근 방식에 대한 완전한 이해를 돕는 데 유용했기를 바랍니다.