Ones

출처: programming challenges

2나 5로 나눌 수 없는 0 이상 10,000 이하의 정수 n이 주어졌는데, n의 배수 중에는 10진수로 표기했을 때 모든 자리 숫자가 1인 것이 있다. 그러한 n의 배수 중에서 가장 작은 것은 몇 자리 수일까?

Sample Input

3
7
9901

Sample Output

3
6
12
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

65개의 풀이가 있습니다. 1 / 7 Page

재귀함수로 짜봤어요 결과는 바로바로 나오네요

def One (n,m=1,k=0,l=0):
    k += m % n
    l += 1
    if k%n == 0: print(l)
    else:One(n,m*10,k,l)

One(3) 
One(7)
One(9997)
이해하기 쉽지 않은 알고리즘이네요, 간단한 설명 좀 부탁드려도 될까요? - 길가의풀, 2014/04/17 14:37 M D
+1 길가의 풀님이 저한테 댓글을.. 영광입니다 ^^; 넵 최대한 설명드릴께요~ 1 = 1 11 = 1 + 10 111 = 1 + 10 + 100 1111 = 1 + 10 + 100 + 1000 이런식 봤을때 7 이 입력 되었을때 1 % 7 = 1 | n = 1 10 % 7 = 3 | n += 3 n = 4 100 % 7 = 2 | n += 2 n = 6 1000 % 7 = 6 | n += 6 n = 12 10000 % 7 = 4 | n += 4 n = 16 100000 % 7 = 5 | n += 5 n = 21 = 111111 ... n이 7의 배수가 되는 순간 나머지가 없으므로 7의 배수가 됩니다 - Starleaguer, 2014/04/17 15:08 M D
설명감사드려요, 이해에 도움이 많이 되었습니다. ^^ - 길가의풀, 2014/04/17 15:40 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Python

def a(n):
    b = '1'
    while int(b) % n != 0: b += '1'
    return len(b)
깔끔하네요 ^^ - 씨니컬우기님, 2016/01/08 10:10 M D
씨니컬우기님, 그렇죠? ㅎㅎ - 이끼소년, 2016/01/10 12:18 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
def ones(n):
    r=1
    while int('1'*r)%n!=0 :r+=1
    return r
우와..... 입력값을 곱해서 1로 이루어지는지를 본 게 아니라 1로 이루어진 수가 입력값으로 나누어지는지를 본 거네요..... 와..... 진짜 짱이다..... - 취미로재미로, 2016/01/27 11:17 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
Algorithm:
(N=1부터 시작해서, 1씩 증가시킴)
입력된 수를 1로만 구성된 N개 자리의 수로 나누는 걸, 나누어질 때까지 반복합니다
package h_Ones;
import java.util.Scanner;
public class Ones {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int L=30;//입력값 수 제한
        int l,i,j,N; long n;
        long input[]=new long[L];
        System.out.println("To stop inputting, input 0.");
        for(l=0;l<L;l++){ input[l]=in.nextLong(); if(input[l]==0) break;} //입력
        for(i=0;i<l;i++){

            /*Algorithm*/
            N=-1;
            do{
                N++;
                n=1; for(j=1;j<N;j++) n=n*10+1; //n= 1로만 이루어진 N자리의 수
            }while(n%input[i]!=0);
            System.out.print(N+" ");
            /*Algorithm ends*/

        } System.out.println("  end. l:"+l);
}}

# 입출력예시
To stop inputting, input 0.
3 7 9901 21 53 47 91 1 111 31 0
3 6 12 6 13 58 6 0 3 15   end. l:10
  • 어떤 수는 연산이 너무 오래걸리거나 작동을 멈춥니다. 9999,9997 등을 입력했더니 프로그램이 작동을 멈춥니다. 다른 알고리즘을 더생각해봐야겠네요
항상 숫자 "1"로 표시되는 수로 수렴하는 것은 아닐 것 같습니다. 9999 같은 경우는 답이 없을수도... - 길가의풀, 2014/03/14 10:14 M D
아.. 다시 해보니 9999는 36, 9997은 192가 나오네요.. 멈추는 이유는 데이터 사이즈 초과 때문이 아닐까요? - 길가의풀, 2014/03/14 11:07 M D
@길가의풀 님 java의 long값의 데이터 용량을 넘겨서 그런가요? 파이썬은 java와 데이터용량체계가 다른가요?;;ㅋㅋ - Katherine, 2014/03/15 15:45 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

파이썬입니다.

배수 증가시키는 부분은 좀 더 개선할 수 있을 것 같습니다. "1"로 이루어진 숫자인지 체크하는 함수는 파이썬 딕셔너리를 이용하여 한번에 찾을 수 있도록 해 봤습니다. 그래도 9901 같은 경우는 4초가량 걸리네요.

import unittest

chk_num = {}
for i in range(1,100): chk_num[int("1"*i)] = ""

def isOne(n):
    if n in chk_num: return True
    return False

def checkOne(no):
    i = 1
    while True:
        n = no * i
        if isOne(n): return len(str(n))
        i += 1

class MyTest(unittest.TestCase):
    def test1(self):
        self.assertEquals(3, checkOne(3))
        self.assertEquals(6, checkOne(7))
        self.assertEquals(12, checkOne(9901))

if __name__ == "__main__":
    unittest.main()

배수증가 시키는 부분을 Katherine 님의 알고리즘으로 변경 해 봤습니다. 훨씬 쾌적하네요 ㅋ

import unittest

chk_num = [int("1"*i) for i in range(1,1000)]
def checkOne(no):
    for c in chk_num:
        if c % no == 0:
            return len(str(c))

class MyTest(unittest.TestCase):
    def test1(self):
        self.assertEquals(3, checkOne(3))
        self.assertEquals(6, checkOne(7))
        self.assertEquals(12, checkOne(9901))
        self.assertEquals(192, checkOne(9997))
        self.assertEquals(36, checkOne(9999))

if __name__ == "__main__":
    unittest.main()
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

파이썬으로 해보았습니다. 입력된 수에 계속 1식 증가한값을 곱하다가 1이나 11,111,1111,11111....등의 수를 만나면 출력하는 방식으로 해보았네요(완전 초보라 어렵네요)

def Chknum(a):
    j = 0
    n = 1
    powSize = 0
    incSize = 1
    m = 0
    while j != n:
        nd = len(str(a))
        n = int(str(1)*nd)
        j = a * m
        m += 1
        if n < j :
            powSize += 1
            incSize = 10**(powSize+nd-1)
            n += incSize
    print len(str(n))

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

파이썬으로 한번 만들어보았습니다. 어떻게하면 더 효율적일지 계속 고민하게되네요.


#
# Return the digit satisfying the given condition
#
def cat_dig(number):
    mul_int = number
    result = False
    while result == False:
        digit = len(str(mul_int))
        if mul_int == int('1' * digit) :
            result = True
        else : result = False
        mul_int += number
    return digit

#
# -------------------------------------------------------
# Check the input is correct
#
while True:
    while True:
        try :
            integer = int(input('Input an positive integer not multiple of 2 or 5 and smaller than 10,000 : '))
            break
        except (TypeError, ValueError) : print("You have to input an ineger")

    if integer >= 10000 or integer <= 0:
        print("This is not a positive integer or is too large")
    elif divmod(integer, 2)[1] == 0 or divmod(integer, 5)[1] == 0:
        print("It is divisible by 2 or 5")
    else :
        break

#
# Run cat_dig(integer) and print the result
#
print(cat_dig(integer))
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

파이썬으로 만들어보았습니다. 나머지 연산을 이용해 자리수 1을 조사하구요 for문에서 짝수배는 11..1같은 수가 나올 수 없으므로 홀수배만 조사하였습니다. 숫자를 입력받을때 짝수이면 바로 없다고 출력하거나 for문에서 5의 배수일 경우 continue시키면 조금 더 빨라질 수도 있을 것 같습니다.

# -*- coding: euc-kr -*-

input_number = input("Input a odd integer between 0 and 10000 : ")  
number = int(input_number)                                          
Max_Multiplier = 100000000                                                                          
for i in range(1, Max_Multiplier + 1, 2):                               
    check_number = number * i                                       
    number_len = len(str(check_number))                                 
    check_answer = 0                                                
    for j in range(1, number_len + 1):                                  
        if((check_number % pow(10, j)) == 1 * pow(10, j - 1)):
            check_number -= pow(10, j-1)                                
            if(j == number_len):                                    
                print(number_len)                                   
                check_answer = 1                            
                break                                               
        else:
            break                                           
    if(check_answer == 1):                                      
        break                                                   
if(check_answer == 0):
    print("%d 배수 내에 해당 숫자가 없습니다" % Max_Multiplier)  
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Ruby

1을 하나씩 늘려가며 해당하는 수의 배수인지 판정합니다.

def ones(target)
  return 0 if target % 2 == 0 or target % 5 == 0
  1.upto(Float::INFINITY).lazy.each {|i| return i if ("1"*i).to_i % target == 0}
end

Test

assert_equal ones(2), 0
assert_equal ones(3), 3
aasert_equal ones(9997), 192
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

파이썬입니다. 재귀함수를 사용했습니다.

def ones(n,allones=0):
        allones = allones * 10 + 1
        if allones % n == 0:
                print("input = %s  result = %s" % (n,len(str(allones))))
        else:
                ones(n,allones)

ones(3)
ones(7)
ones(9901)
ones(1)
ones(9997)
ones(9999)

test 내용은 아래와 같습니다.

input = 3  result = 3
input = 7  result = 6
input = 9901  result = 12
input = 1  result = 1
input = 9997  result = 192
input = 9999  result = 36
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.


언어별 풀이 현황
전 체 x 65
java x 12
scala x 2
python x 38
cpp x 1
기 타 x 6
matlab x 1
cs x 3
php x 1
ruby x 1