숫자 N이 주어졌을 때, 목표는 [1, N] 범위 내에서 자릿수 중 0을 하나라도 포함하는 숫자의 개수를 구하는 것입니다.
이 문제는 숫자를 처음부터 끝까지 하나씩 검사하는 방식으로 해결할 수 있습니다. 한 자리 숫자(1~9)에는 0이 존재할 수 없으므로, 실질적으로는 10부터 N까지만 확인하면 됩니다. 각 숫자에 대해 while 루프를 사용해 모든 자릿수를 검사하고, 0인 자릿수를 발견하면 카운트를 증가시킨 뒤 다음 숫자로 넘어갑니다. 0이 아니라면 숫자를 10으로 나누어 다음 자릿수를 검사하고, 이 과정은 남은 숫자가 없을 때까지 반복합니다.
예시를 통해 자세히 살펴보겠습니다.
입력 예시 1
N = 11
출력
Numbers from 1 to N with 0 as digit: 1
설명: 10부터 11까지 확인하면 0을 자릿수로 가지는 숫자는 10뿐입니다. 1~9는 확인할 필요가 없습니다.
입력 예시 2
N = 100
출력
Numbers from 1 to N with 0 as digit: 10
설명: 10, 20, 30, 40, 50, 60, 70, 80, 90, 100으로 총 10개의 숫자가 0을 자릿수로 가집니다.
문제 해결 접근 방법
- 정수 N을 입력받습니다.
haveZero(int n)함수는 n을 매개변수로 받아, 0을 자릿수로 포함하는 숫자의 개수를 반환합니다.- 조건을 만족하는 숫자의 개수를 저장할
count변수를 0으로 초기화합니다. for루프를 사용해 i = 1부터 i = n까지 숫자를 순회합니다. (1~9에는 0이 없으므로 결과에는 영향을 주지 않습니다.)- 각 숫자
num = i에 대해while루프로num % 10 == 0여부를 확인합니다. 거짓이라면num을 10으로 나누어 다음 자릿수를 검사하고,num > 0인 동안 반복합니다. - 자릿수가 0이면 더 이상 검사하지 않고
count를 증가시킨 후break로 루프를 종료합니다. (중복 계산 방지) - 모든 루프가 종료되면
count에는 1부터 N 사이에서 0을 자릿수로 가지는 숫자의 총개수가 저장됩니다. - 최종 결과로
count를 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int haveZero(int n){
int count = 0;
for (int i = 1; i <= n; i++) {
int num = i;
while(num>1){
int digit=num%10;
if (digit == 0){
count++;
break;
}
else
{ num=num/10; }
}
}
return count;
}
int main(){
int N = 200;
cout <<"Numbers from 1 to N with 0 as digit: "<<haveZero(N);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Numbers from 1 to N with 0 as digit: 29
N = 200일 때, 0을 자릿수로 포함하는 숫자는 총 29개입니다. (예: 10, 20, ..., 100, 101, 102, ... 등)
시간 복잡도
각 숫자의 자릿수 검사는 최대 O(log₁₀ N)번의 연산이 필요하므로, 전체 시간 복잡도는 O(N × log₁₀ N)입니다. N이 크다면 자릿수 조합을 활용한 수학적 접근으로 더 효율적으로 최적화할 수 있습니다.