유한소수 판별하기

https://school.programmers.co.kr/learn/courses/30/lessons/120878

프로그래머스

---

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

기약분수로 나타내었을 때, 분모의 소인수가 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

---

입출력 예 설명
입출력 예 #1

• 분수 7/20은 기약분수 입니다. 분모 20의 소인수가 2, 5 이기 때문에 유한소수입니다. 따라서 1을 return합니다.

입출력 예 #2

• 분수 11/22는 기약분수로 나타내면 1/2 입니다. 분모 2는 소인수가 2 뿐이기 때문에 유한소수 입니다. 따라서 1을 return합니다.

입출력 예 #3

• 분수 12/21는 기약분수로 나타내면 4/7 입니다. 분모 7은 소인수가 7 이므로 무한소수입니다. 따라서 2를 return합니다.

---

Hint

• 분자와 분모의 최대공약수로 약분하면 기약분수를 만들 수 있습니다.
• 정수도 유한소수로 분류합니다.

---

기약분수가 유한소수인지, 무한소수인지 분류하는 문제입니다.

문제에서 친절하게 유한소수의 조건을 알려주었네요. 먼저 기약분수를 만든 다음, 분모를 확인하면 될 것 같습니다.

 

파이썬으로 문제를 풀어보겠습니다

from math import gcd
def solution(a, b):
    # 최대공약수 g를 찾습니다.
    g = gcd(a, b)
    # 기약분수로 변환합니다.
    na, nb = a // g, b // g
    
    # 분모에서 2와 5가 사라질 때까지 반복합니다.
    while nb % 2 == 0:
        nb //= 2
    while nb % 5 == 0:
        nb //= 5

    # 유한소수는 1, 무한소수는 2로 반환합니다.
    return 1 if nb == 1 else 2

먼저 기약분수를 만들기 위해 Hint에 나와있듯 최대공약수를 찾습니다.

파이썬에서는 math 패키지에서 gcd(최대공약수), lcm(최소공배수)를 제공하기 때문에, gcd 함수를 사용해서 최대공약수 g를 구합니다.

분자 a, 분모 b를 최대공약수로 나눠주면 기약분수의 분자 na, 분모 nb를 얻을 수 있습니다. 사실 na는 구할 필요는 없지만 그냥 구해봤습니다.

 

그다음, 이제 nb에서 2와 5가 사라질 때까지 반복합니다.

유한소수에서는 nb가 2와 5로만 이뤄져있기 때문에, 정수에서는 nb가 1이기 때문에 while문을 실행하면 nb가 최종적으로 1이 됩니다.

반대로 무한소수는 nb가 2와 5 이외의 숫자로 이뤄졌기 때문에 nb가 최종적으로 1이 될 수가 없습니다.

 

따라서 nb의 최종값에 따라서 1이라면 유한소수이므로 1을, 1 이외의 값이라면 무한소수이므로 2를 반환합니다.

 

재미있는 문제였습니다.