1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | #include <iostream> #include <set> using namespace std; bool repeatless(unsigned int number) { set<int> sNumber; bool how = true; if (number < 10) return true; else { while (number != 0) { how = sNumber.insert(number % 10).second; if (how == false) return false; number /= 10; } return true; } } int main() { unsigned int number = -1; while (number) { cin >> number; unsigned int i = 0; for (unsigned int j = 1; j <= number;j++) { i++; if (repeatless(i) != true) j--; //else // cout << i<<" "; } if(number != 0) cout << i << endl; } } | cs |
d제가 algospot이라는 사이트에서 아무 알고리즘 문제 잡아서 푸는 연습을 하고있습니다.
문제의 요지는 같은 수가 반복되지 않는 숫자 중 내가 입력한 n번째의 숫자를 결과로 나타내는 것 입니다.
예를 들어 반복되지 않는 숫자를 RN(Repeatless Number)이라 하면 21, 123, 26057 과 같은 숫자는 RN이고
11, 121, 10100, 14141과 같은 숫자는 RN이 아닙니다.
따라서 25를 입력하면 RN이 아닌 11과 22를 제외 한 자연수 중 25번째 문자인 27이 결과로 나오게 됩니다.
문제를 고심해서 풀었고 위와 같은 코드로 컴파일을 해보니 값은 정확하게 나옵니다. (ex, 10000을 입력하면 26057)
하지만 문제는 프로그램 효율성이 너무 떨어져서 높은 값을 입력하면 결과가 너무 느리게 나오네요 ㅠㅠ
프로그램 효율성을 높이는 방법이 무엇이 있을까요?? 이것에 대해 생각해보고 제대로 공부해본 적이 없어서 어떻게 해야할지 모르겠네요 ㅠ..
십만을 입력하니 10초 조금 넘게 지나니까 답을 내내요...
