구간 [first, last]가 주어졌을 때, 이 구간 안에서 첫 번째 자릿수와 마지막 자릿수가 같은 숫자의 개수를 구하는 것이 목표입니다. 예를 들어 232는 첫 자릿수와 마지막 자릿수가 모두 2로 동일합니다.
해결 방법은 간단합니다. i = first부터 i = last까지 차례대로 순회하면서, 각 숫자의 첫 자릿수와 마지막 자릿수를 비교하고, 두 값이 같다면 카운트를 증가시키면 됩니다.
예제로 이해하기
입력 − first = 8, last = 40
출력 − 첫 자릿수와 마지막 자릿수가 같은 숫자의 개수 − 5
설명 − 8부터 40 사이에서 조건을 만족하는 숫자는 다음과 같습니다.
8, 9, 11, 22, 33
입력 − first = 100, last = 200
출력 − 첫 자릿수와 마지막 자릿수가 같은 숫자의 개수 − 10
설명 − 100부터 200 사이에서 조건을 만족하는 숫자는 다음과 같습니다.
101, 111, 121, 131, 141, 151, 161, 171, 181, 191
프로그램에 적용한 접근 방식
- 두 정수 first와 last를 입력받아 범위 [first, last]를 정의합니다.
- 함수 getFirstDigit(int num)는 전달받은 숫자의 첫 자릿수를 반환합니다.
- num이 10보다 크거나 같은 동안 num을 10으로 계속 나누면, 반복이 끝난 뒤 num에는 첫 자릿수만 남게 됩니다. 이 값을 반환합니다.
- 함수 getCount(int fst, int lst)는 범위를 받아 해당 구간 내에서 첫 자릿수와 마지막 자릿수가 같은 숫자의 개수를 반환합니다.
- 카운트 변수의 초기값은 0으로 설정합니다.
- for 루프를 사용해 i = fst부터 i = lst까지 순회하면서, 각 숫자 i에 대해 getFirstDigit(i)를 호출하여 첫 자릿수를 fdigit에 저장합니다. (fdigit = getFirstDigit(i))
- 마지막 자릿수는 ldigit = i % 10으로 계산합니다.
- ldigit == fdigit이라면 두 자릿수가 같다는 의미이므로 카운트를 증가시킵니다.
- 최종적으로 카운트를 결과로 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
// 첫 자릿수를 구하는 함수
int getFirstDigit(int num){
while (num >= 10)
{ num = num / 10; }
return num;
}
int getCount(int fst, int lst){
int count = 0;
for(int i = fst; i <= lst; i++){
int fdigit = getFirstDigit(i); // 첫 자릿수
int ldigit = i % 10; // 마지막 자릿수
if(fdigit == ldigit) // 두 값이 같으면 카운트 증가
{ ++count; }
}
return count;
}
int main(){
int first = 10, last = 23;
cout << "첫 자릿수와 마지막 자릿수가 같은 숫자의 개수: " << getCount(first, last);
return 0;
}출력 결과
위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다.
첫 자릿수와 마지막 자릿수가 같은 숫자의 개수: 2
이처럼 각 숫자를 일일이 확인하는 방법은 시간 복잡도가 O(N)으로 단순하지만 직관적입니다. 참고로, 수학적 공식을 활용하면 구간 내 조건을 만족하는 숫자의 개수를 O(1)에 가깝게 계산할 수도 있으므로, 범위가 매우 클 경우 최적화를 고려해볼 만합니다.