이번 글에서는 자릿수 d와 상한값 n이 주어졌을 때, 0부터 n 사이의 범위에서 숫자 d를 하나라도 포함하는 모든 수를 찾아보겠습니다.
예를 들어 n = 20이고 찾고자 하는 숫자가 3이라면, 해당 조건을 만족하는 숫자는 [3, 13] 두 개입니다.
해결 방법
이 문제를 해결하는 가장 간단한 방법은 각 숫자를 문자열로 변환한 뒤, 그 문자열 안에 목표 자릿수 d가 존재하는지 확인하는 것입니다. 문자열에 d가 포함되어 있다면 해당 숫자를 출력하고, 포함되어 있지 않다면 무시하면 됩니다.
구체적인 알고리즘은 다음과 같습니다.
- 자릿수 d를 문자열로 변환하여 검색용 문자 p를 만듭니다.
- 0부터 n까지의 모든 숫자 i에 대해 반복합니다.
- 각 숫자 i를 문자열로 변환한 후 find() 함수를 사용해 p가 포함되어 있는지 확인합니다.
- p가 발견되면 해당 숫자를 출력합니다.
C++ 예제 코드
#include<iostream>
using namespace std;
int getAllNumWithDigit(int n, int d) {
string str = "";
str += to_string(d);
char ch = str[0];
string p = "";
p += ch;
for (int i = 0; i <= n; i++) {
str = "";
str = str + to_string(i);
int index = str.find(p);
if (i == d || index!=-1)
cout << (i) << " ";
}
}
int main() {
int n = 100; int d = 3;
getAllNumWithDigit(n, d);
}실행 결과
위 코드를 실행하면 n = 100, d = 3일 때 다음과 같은 결과를 얻을 수 있습니다.
3 13 23 30 31 32 33 34 35 36 37 38 39 43 53 63 73 83 93
출력 결과를 보면 일의 자리 또는 십의 자리에 숫자 3을 포함하는 모든 수가 정확히 출력된 것을 확인할 수 있습니다.
코드 설명
- to_string(d): 자릿수 d를 문자열로 변환합니다.
- str.find(p): 문자열 str에서 부분 문자열 p를 검색하며, 찾으면 해당 인덱스를, 못 찾으면 -1을 반환합니다.
- i == d: 한 자리 숫자인 경우에도 정확하게 처리하기 위한 조건입니다.
이 방식은 시간 복잡도가 O(n × k)입니다. 여기서 k는 각 숫자를 문자열로 변환하고 검색하는 데 드는 비용으로, 숫자의 자릿수 길이에 비례합니다. 구현이 매우 직관적이고 간단하기 때문에 입력 범위가 크지 않은 경우에 효율적으로 사용할 수 있습니다.