2009. 6. 2. 20:31

f(n) = n 찾기 퀴즈

우연찮게 성윤이 블로그에 구글입사문제라는 퀴즈를 봤습니다. 일도 많은데, 저도 모르게 막 풀고 있어 덕분에 야근 하고 있습니다. 풀기는 풀었는데, 좀 오래걸렸네요.

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

간단하게 f(n) = f(n-1) + (n값의 1이 나온횟수)
를 이용해서 recursive call을 쓰면 될줄 알았는데, 값이 커지면 StackOver가 나오더군요. n값을 그냥 문자열로 변환해서 1을 세는 부분도 값이 커지니까 문제가 되었습니다..

그래서 열심히 짱구를 굴려 그냥 내장 연산자를 사용했습니다.

 public int oneCount(int n) {
  if(n <= 0) {
   return 0;
  }
  
  boolean result = true;
  int sum = 0;
  while(result) {
   sum += n % 10 == 1 ? 1 : 0;
   n = n / 10;
   result = n > 0 ? true : false;
  }
  return sum;
 }
10으로 나눈 나머지 값을 비교하는 룰을 사용했습니다.

 public int f(int n) {
  int result = 0;
  for(int i = n; i > 0 ; i--) {
   result += oneCount(i);
   
   if(index == n - 1) {
    result += value;
    break;
   }

  }
  
  index = n;
  value = result;
  return result;
 }

f(n)은 값은 f(n-1)값을 사용 함으로 n값을 순차적으로 올려 최소값을 찾을때 속도가 아주 좋아졌습니다.

 @Test public void testOneCount() {
  Assert.assertEquals(1, oneCount(1));
  Assert.assertEquals(0, oneCount(2));
  Assert.assertEquals(0, oneCount(9));
  Assert.assertEquals(1, oneCount(10));
  Assert.assertEquals(0, oneCount(999));
  Assert.assertEquals(3, oneCount(111));
  Assert.assertEquals(1, oneCount(100));
  Assert.assertEquals(0, oneCount(200));
  Assert.assertEquals(1, oneCount(1234567890));
  Assert.assertEquals(0, oneCount(9368));
 }
 
 @Test public void testF() {
  Assert.assertEquals(1, f(1));
  Assert.assertEquals(7, f(14));
  Assert.assertEquals(199981, f(199981));
 }

 @Test
 public void testFindValue() {
  int index = 2;
  while(f(index) != index) {
   index++;
   if(index == 1000000) {
    index = -1;
    break;
   }
  }
  System.out.println(index);
 }




이제 구글 입사하면 되나요? ㅋㅋㅋ