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);
 }




이제 구글 입사하면 되나요? ㅋㅋㅋ
Trackback 0 Comment 8
  1. 박성철 2009.06.02 22:21 address edit & del reply

    축!

  2. 박성철 2009.06.02 22:26 address edit & del reply

    나도 재미삼아 만들어 보기는 했는데 뭔가 기똥찬면이 결여되어 있네요. 뭐가 없을지...

  3. is윤군 2009.06.02 22:45 신고 address edit & del reply

    떙!!!ㅋㅋ

    • 소내기 2009.06.02 23:33 address edit & del

      떨어진겨? ㅋㅋ

    • is윤군 2009.06.02 23:36 신고 address edit & del

      일단 제가 먼저 입사하고 ..ㅋㅋ 합격시켜줄게요;;ㅋㅋ

  4. 박성철 2009.06.03 11:11 address edit & del reply

    근데 잴씨는 왜 자기 블로그에 안 올리고 스터디 블로그에...;;;

    • is윤군 2009.06.03 13:00 신고 address edit & del

      머 어때요 ..ㅋ 안그래도 조용하던 블로그였는걸요;;ㅋ

  5. 소내기 2009.06.03 17:26 신고 address edit & del reply

    자랑할라고요--;ㅋ