구간 [first, last]가 주어졌을 때, 목표는 이 범위 안에 속하면서 일의 자릿수가 k인 숫자가 총 몇 개인지 세는 것입니다.
가장 직관적인 방법은 first부터 last까지 숫자를 하나씩 확인하는 것입니다. 각 숫자 i에 대해 i % 10으로 일의 자릿수를 구한 뒤, 그 값이 k와 같으면 카운트를 1 증가시키면 됩니다.
구체적인 예제를 통해 살펴보겠습니다.
입력 − first=8, last=40, k=8
출력 − 일의 자릿수가 k인 숫자의 개수 − 4
설명 −
8과 40 사이에서 일의 자릿수가 8인 숫자 8, 18, 28, 38
입력 − first=100, last=200, k=9
출력 − 일의 자릿수가 k인 숫자의 개수 − 10
설명 −
100과 200 사이에서 일의 자릿수가 9인 숫자 109, 119, 129, 139, 149, 159, 169, 179, 189, 199 총 10개
프로그램에 사용된 접근 방식
두 정수 first와 last를 입력받아 탐색 범위 [first, last]를 정의합니다.
getCount(int fst, int lst, int k) 함수는 범위 변수와 k를 매개변수로 받아, fst부터 lst 사이에서 일의 자릿수가 k인 숫자의 개수를 반환합니다.
초기 count 값을 0으로 설정합니다.
for 반복문을 사용해 i=fst부터 i=lst까지 순회하면서, 각 i에 대해 ldigit = i % 10 연산으로 일의 자릿수를 계산합니다.
ldigit과 k가 같으면 count를 1 증가시킵니다.
순회가 끝나면 count를 결과값으로 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int getCount(int fst, int lst, int k){
int count = 0;
for(int i = fst; i <= lst; i++){
int ldigit = i % 10; // 일의 자릿수 구하기
if(ldigit == k) // 일의 자릿수가 k와 같으면 카운트 증가
{ ++count; }
}
return count;
}
int main(){
int first = 5, last = 30;
int K = 5;
cout<<"범위 내 일의 자릿수가 K인 숫자의 개수:"<<getCount(first, last, K);
return 0;
}출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
범위 내 일의 자릿수가 K인 숫자의 개수:3
즉, 5부터 30 사이에서 일의 자릿수가 5인 숫자는 5, 15, 25로 총 3개입니다.
복잡도 분석
이 방법은 범위의 모든 숫자를 한 번씩 확인하므로 시간 복잡도는 O(N)(N은 범위의 크기)입니다. 범위가 작다면 충분히 효율적이지만, 범위가 매우 넓은 경우에는 수학적 공식을 활용해 O(1)에 가깝게 최적화할 수도 있습니다.