엽기민원의 場

좋은 경험이라고 해야 하나, "구글" 인터뷰 때문에 했던 각종 문제 풀이를 포스팅 해놨는데 공개하지 않았었다. 뭐 시간도 많이 지났고 하니 그 당시 풀었던 문제를 공개해본다.

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

저도 한번 풀어봤습니다.
먼저 다음과 같이 규칙이 있더군요.



아 대충 보이지요 ^^ 정리해보겠습니다.

f(n)  라고 정의 하고,  n = a * 10 ** c + b, a는 첫번째 자리의 숫자, c는 기수, b는 그외의 나머지 숫자라고 합시다.
case1 : a == 1일때
f(a * 10 ** (c-1) + b) = f(10 **(c-1) -1) + b + 1 + f(b)
case2 : a != 1 일때
f(a * 10 ** (c-1) + b) =a * f(a * 10 ** (c-1) - 1) +  10 ** (c-1) + f(b)

자 이제 함수가 대충 완료되었습니다. 재귀함수로 쉽게 만들수 있습니다.

def sum_one(num)
  num_string = num.to_s
  c = num_string.length
  a = num_string[0] - 48 # 'a'->48
  b = num_string[1..(num_string.length - 1)].to_i

  if(num == 0)
    sum = 0
  elsif(num < 10)
    sum = 1
  else
    if a == 1
      sum = sum_one(10 ** (c - 1) - 1)
      sum += b + 1
      sum += sum_one(b)
    else
      sum = a * sum_one(10 ** (c - 1) - 1)
      sum += 10 ** (c - 1)
      sum += sum_one(b)
    end
  end
  sum
end

자 함수는 구현되었습니다. 재귀함수로 자릿수에 비례해서 재귀를 하게됩니다. 이게 계산속도 저하를 가져오는데요. 재귀를 하기 때문이죠. 근데 재미있는 건, 재귀하는 인수들의 모습이 대략 f(9), f(99), f(999)의 형식입니다. 왜냐면 10 ** (c - 1) - 1의 형식이깐요.
낚시광준초리 님이 여기서 언급한거 처럼 그 함수는 f(10 ** (c -1) -1) = c * 10 ** (c-1)입니다.
이런 것들은 첫자리수가 1이 아니므로 두번째 케이스를 풀어내면 나오는 식입니다.
다시 풀어보면 n = 10 ** (c -1) -1 이라고 할때..
f(n) = (n-1)log 1o (n-1) / 10 입니다. 아무튼 이런 값들은 재귀를 보내지 말고 그냥 계산해도 될껍니다. ^^ 그래서 추가해줍니다.

def sum_one(num)
  num_string = num.to_s
  c = num_string.length
  a = num_string[0] - 48 # 'a'->48
  b = num_string[1..(num_string.length - 1)].to_i

  if(num == 0)
   sum = 0
  elsif(num < 10)
   sum = 1
  elsif(10 ** (c-1) - 1 == num)
    sum = num.length * (10 ** c )
  else
   if a == 1
     sum = sum_one(10 ** (c - 1) - 1)
     sum += b + 1
     sum += sum_one(b)
   else
     sum = a * sum_one(10 ** (c - 1) - 1)
     sum += 10 ** (c - 1)
     sum += sum_one(b)
   end
  end
  sum
end

이렇게 되면 재귀한두번 만에 거의 답이 나옵니다. 이제 첫번째 조건에 맞는 양의 정수를 찾아봅시다.

좀더 무조건 돌려보는 것도 일종의 방법이 될수 있으나, 몇가지 고려로 수를 찾는 방법을 옵티마이즈 해봅시다.
이것은 먼저 N(n) = n의 함수와 F(n)의 그래프 추이를 보면 대충 보면 수를 찾을수 있는 방법이 나옵니다.

(1..100).each do |c|
  ((10**(c-1))..(2*10**(c-1) -1)).each do |m| 
    if sum_one(m) == m
      puts m
    end
  end
end

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

Posted by 엽기민원