두 개의 양의 정수 n과 k가 주어졌을 때, 숫자 k를 포함하거나 k로 나누어 떨어지는 수들 중 n번째 수를 찾는 것이 이 글의 목표입니다. 단, k의 범위는 2부터 9 사이로 제한됩니다.
예를 들어 n이 15이고 k가 3이라면 결과값은 33입니다. 그 이유는 [3, 6, 9, 12, 13, 15, 18, 21, 23, 24, 27, 30, 31, 33]처럼 각 숫자가 자릿수에 3을 포함하거나 3으로 나누어 떨어지는 수들이며, 이 중 15번째 수가 바로 33이기 때문입니다.
문제 해결 접근 방법
가장 직관적인 방법은 다음과 같습니다.
- 1부터 시작하여 차례대로 각 숫자를 검사합니다.
- 현재 숫자에 자릿수 k가 포함되어 있는지 확인합니다.
- 또는 현재 숫자가 k로 나누어 떨어지는지 확인합니다.
- 조건을 만족할 때마다 카운트를 증가시키고, 카운트가 n에 도달하면 해당 숫자를 반환합니다.
C++ 구현 코드
#include<iostream>
using namespace std;
// 숫자 n에 자릿수 k가 포함되어 있는지 검사하는 함수
bool hasDigit(int n, int k) {
while (n > 0) {
int rem = n % 10;
if (rem == k)
return true;
n = n / 10;
}
return false;
}
// 조건을 만족하는 n번째 숫자를 찾는 함수
int countNumbers(int n, int k) {
for (int i = k + 1, count = 1; count < n; i++) {
if (hasDigit(i, k) || (i % k == 0))
count++;
if (count == n)
return i;
}
return -1;
}
int main() {
int n = 10, k = 2;
cout << "Last number is " << countNumbers(n, k) << " before that the number contains " << k << " and multiple of " << k;
}실행 결과
Last number is 20 before that the number contains 2 and multiple of 2
코드 상세 설명
1. hasDigit 함수
이 함수는 주어진 정수 n의 각 자릿수를 하나씩 추출하여 k와 일치하는지 확인합니다. 10으로 나눈 나머지(%)를 이용해 가장 오른쪽 자릿수를 얻고, 10으로 나누어(/) 다음 자릿수로 이동하는 방식을 반복합니다. 모든 자릿수를 검사한 후에도 k가 없다면 false를 반환합니다.
2. countNumbers 함수
k 자체가 첫 번째 조건 만족 수이므로, 반복문은 k+1부터 시작하고 초기 카운트를 1로 설정합니다. 이후 각 숫자에 대해 hasDigit(i, k)(자릿수 포함 여부) 또는 i % k == 0(배수 여부) 조건 중 하나라도 참이면 카운트를 증가시킵니다. 카운트가 n에 도달하는 순간 해당 숫자를 반환합니다.
시간 복잡도 분석
이 알고리즘은 조건을 만족하는 수를 하나씩 선형 탐색하므로, 최악의 경우 시간 복잡도는 O(n × d)입니다. 여기서 d는 검사하는 숫자의 자릿수입니다. 자릿수 검사는 숫자의 길이에 비례하기 때문에, n이 매우 커질 경우 실행 시간이 늘어날 수 있습니다.
마무리
이 문제는 단순한 반복문과 자릿수 분해 기법만으로 해결할 수 있는 대표적인 구현 유형 문제입니다. 나머지 연산과 나눗셈을 활용한 자릿수 추출 방법은 다양한 코딩 테스트에서 자주 활용되므로, 이 예제를 통해 개념을 확실히 익혀두면 좋습니다.