문제
a부터 b까지의 방 번호 중 모든 자릿수가 서로 다른 번호의 개수를 구하라.
입력
여러 줄에 걸쳐 a와 b가 주어진다 (EOF까지).
출력
각 줄마다 조건을 만족하는 방 번호의 개수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
1 10 | 10 |
풀이
범위 내 각 수의 자릿수 중복 여부를 확인한다.
- a부터 b까지 각 수를 문자열로 변환한다
- 각 자릿수의 출현 횟수를 배열로 세어 2 이상인 것이 있는지 확인한다
- 모든 자릿수가 서로 다르면 카운트한다
핵심 아이디어: 0~9 빈도 배열로 중복을 O(자릿수)에 판별할 수 있다.
코드
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
int main()
{
int a, b;
int cnt1;
int cnt2;
while (scanf("%d%d", &a, &b) != EOF)
{
cnt1 = 0;
cnt2 = 0;
for (int i = a; i <= b; i++)
{
cnt1++;
int cnt = 0;
int arr[10] = {0};
string str = to_string(i);
for (int i = 0; i < str.length(); i++)
{
cnt = str[i] - '0';
arr[cnt]++;
}
for (int i = 0; i < 10; i++)
{
if (arr[i] >= 2)
{
cnt2 += 1;
break;
}
}
}
cout << cnt1 - cnt2 << "\n";
}
return 0;
}복잡도
- 시간: O((b - a) * d) (d: 자릿수)
- 공간: O(1)