[코딩테스트 입문]Day22-3

유한소수 판별하기

문제 설명

소수점 아래 숫자가 계속되지 않고 유한개인 소수를 유한소수라고 합니다. 분수를 소수로 고칠 때 유한소수로 나타낼 수 있는 분수인지 판별하려고 합니다. 유한소수가 되기 위한 분수의 조건은 다음과 같습니다.

• 기약분수로 나타내었을 때, 분모의 소인수가 2와 5만 존재해야 합니다.

두 정수 a와 b가 매개변수로 주어질 때, a/b가 유한소수이면 1을, 무한소수라면 2를 return하도록 solution 함수를 완성해주세요.

---

제한사항

• a, b는 정수
• 0 < a ≤ 1,000
• 0 < b ≤ 1,000

---

입출력 예

a	b	result
7	20	1
11	22	1
12	21	2

풀어보기

def solution(a, b):
    if a % b == a and b % a == 0:
        b = b // a
    elif a % b == 0:
        return 1

    while b % 2 == 0 or b % 5 == 0:
        if b % 2 == 0:
            b = b / 2
        elif b % 5 == 0:
            b = b / 5
    return int(b != 1) + 1

실패인 테스트 케이스 발생.

다시 풀어봅시다.

def solution(a, b):
    # n = 2
    # s = []
    answer = []
    for i in [a, b]:
        c = i
        n = 1
        s = []
        while n <= i:
            if c % n == 0:
                if n == 1:
                    s.append(n)
                    n += 1
                else:
                    c //= n
                    s.append(n)
            else:
                n += 1
        answer.append(s)

    l1 = [1] + [_ for _ in answer[0] if _ not in answer[1]]
    l2 = [1] + [_ for _ in answer[1] if _ not in answer[0]]

    if len(l2) != 1:
        for _ in l2:
            if _ not in [1, 2, 5]:
                return 2
        return 1

실패 했습니다..ㅠㅠ 다시 시도!

from fractions import Fraction


def solution(a, b):
    F = Fraction(a, b)
    s = F.denominator
    n = 2
    new = []
    v = s
    while n < s+1:
        if v % n == 0:
            v /= n
            new.append(n)
        else:
            n += 1
    for _ in new:
        if _ not in [2, 5]:
            return 2
    return 1

Fraction모듈을 사용해서 풀었습니다.!!(‾◡◝)

Fraction(a, b)하면 a/b로 나옵니다.
분수.numerator = 분자, 분수.denominator = 분모입니다.

---

다른 풀이

---

첫 번째

from math import gcd
def solution(a, b):
    b //= gcd(a,b)
    while b%2==0:
        b//=2
    while b%5==0:
        b//=5
    return 1 if b==1 else 2

gcd는 최대공약수이며 (7, 20)이면 gcd(7,20) = 1입니다.

이것을 보고 위에 Fraction을 사용한 식을 고쳐봤습니다.

from fractions import Fraction

def solution(a, b):
    F = Fraction(a, b)
    s = F.denominator
    while s % 2 == 0:
        s //= 2
    while s % 5 == 0:
        s //= 5
    return int(s != 1) + 1

두 번째

from math import gcd

def solution(a, b):
    b = b / gcd(a, b)
    for i in [2, 5]:
        while not b % i:
            b //= i

    return 1 if b == 1 else 2

---

최대공약수, 최소공배수 (gcd, lcm)

1. 최대공약수 함수(gcd)

gcd함수는 math라이브러리에 속해있습니다. 그래서 사용할 때는 from math import gcd를 작성합니다.

math.gcd(숫자들)
a와 b의 최대공약수를 구하는 것 입니다. 최대공약수는 둘 이상의 정수의 공약수 중에서 가장 큰 것입니다.
greatest common divisor입니다.

2. 최소공배수 함수(lcm)

lcm 함수도 math라이브러리에 속해있습니다. from math import lcm으로 사용합니다.

math.lcm(숫자들)
인자로 들어온 숫자들의 최소공배수를 반환합니다.
least common multiple을 줄여서 lcm입니다. 둘 이상의 정수의 공배수 중에서 가장 작은 것을 말합니다.

(7, 20)의 최소공배수를 구하면 lcm(7, 20) = 140입니다.