이게 구글 시험이라구??

우연히 구글입사에 관한 글을 보다가 구글이 알고리즘을 중요시한다는 글을 보았다.
인터넷에 가장 많이 올라와 있는 구글 문제를 풀어보게 되었는데,
답이 나오는 것 보다 얼마나 최적화를 잘 시키는지가 관건이라고 할 수 있겠다.
재귀함수로 10씩 나누면서 1자리에 있는 값이 1인지 체크하는 식으로 카운트를 했다.
현재 내 컴퓨터에서 소요시간은 0.031초가 나온다.

문제.
양의 정수 n에 대해서 1과 n 사이에 1이 나오는 횟수를 나타내는 함수를 f(n)이라고 한다. 예를 들어 f(13)=6이다.
f(n)=n이 되는 첫번째 양수는 1이다. 두번째 양수는 무엇인가.

답.
199981

int countOne(int n) {
 int nTemp = ((n%10)==1)? 1 : 0;
 if(n>9)
  return nTemp + countOne(n/10);
 else
  return nTemp;
}

void main( ) {
 int nCount = 0, nFind = 0;
 int nCur = 0 , nPre = 0;
 clock_t time;
 time = clock();

 while(true) {
  ++nCount;
  nCur = countOne(nCount) + nPre;
  if(nCount == nCur)
   if(++nFind == 2)
    break;
  nPre = nCur;
 }

 cout << nCount << endl;
 time = clock() - time;
 cout << "time : "<< (double)time/CLOCKS_PER_SEC << endl;
}