출처
- https://algospot.com/judge/problem/read/REPEATLESS
난이도
- (하) – 중 – 상 – 최상 – 풀지 못함
문제 (항상 대략적인 설명만 작성합니다. 문제는 위 출처에서 확인하세요)
- Repeatless한 숫자들의 순서를 찾는 문제이다. 예를 들어 123은 1, 2, 3이 한 번씩만 존재하기 때문에 Repeatless 숫자이다. 반면 1233의 경우 3이 2번 나오기 때문에 Repeatless 숫자가 아니다. Input으로 100이란 숫자가 주어지면, 1부터 시작하여 100번째 Repeatless 수를 찾는 문제이다.
후기
- 단순 문제 난이도를 보면 최하 수준 정도로 아주 쉬운 문제라고 판단된다. 하지만, 제일 빠른 코드들은 1ms 이하에서 모든 문제를 해결하는 것으로 확인하였다. 결과적으로 내가 푼 방법보다 빠른 알고리즘이 존재하는데 잘 모르겠다. 빠른 알고리즘들을 확인할 수 없다는 게 조금 아쉽다.
- 최대 입력의 수가 정해져 있어서 처음부터 최대 입력 수까지의 모든 Repeatless 수를 만들어서 Cache에 저장하였다. 그리고 Input이 주어지면 단순히 Cache에서 답을 찾아서 출력하는 방법으로 문제를 해결하였다. 수를 만드는 방법은 계속 10으로 나누어 나머지 값을 계산하는 방식을 선택하였다.
- 나머지의 값이 한 번이라도 나온 적이 있는지 확인하기 위해서 Bit 연산 사용하였다. & (And) 와 | (Or) 연산이 아직 익숙하지 않아서 몇 번 실수는 했지만, Bit 연산을 연습 할 수 있었던 좋은 문제라고 생각한다.
코드
- 총 1000000개의 Repeatless 수를 모두 생성하는 방법으로 문제 해결하는 코드
- 실행 시간: 548ms (제일 빠른 코드 대비 548배 (1ms) 느림. 다른 사람의 Solution을 확인할 수 없어서 아쉽다)
#include <stdio.h>
//MK: Visual Studio를 사용시 scanf 에러 제거함.
#pragma warning(disable:4996)
#define MAXSIZE 1000001
int cache[MAXSIZE];
//MK: 최대 Input에 대한 모든 Repeatless 번호를 생성하는 부분
void init() {
int i = 1;
int ptr = 1;
while (i < MAXSIZE) {
int tmp = ptr;
int visited = 0;
while (tmp > 0) {
int reminder = tmp % 10;
//MK: 나머지 값들을 확인하여 이전에 나온 숫자인지 확인함
if ((visited & (1 << reminder)) == 0) {
visited |= (1 << reminder);
}
else {
break;
}
tmp /= 10;
}
if (tmp == 0) {
cache[i] = ptr;
i++;
}
ptr++;
}
}
int main() {
//freopen("input.txt", "r", stdin);
init();
while (1) {
int tmp;
scanf("%d", &tmp);
if (tmp == 0) {
break;
}
printf("%d\n", cache[tmp]);
}
return 0;
}