[프로그래머스][Lv.0] 유한소수 판별하기*

문제

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

프로그래머스

 

내 풀이

def solution(a, b):
    gcd = getGcd(a, b)
    target = b // gcd
    
    l = []
    x = 2
    while target != 1:
        if target % x == 0:
            l.append(x)
            target /= x
            x = 2
        else:
            x += 1

    l = list(set(l))

    if 2 in l:
      l.remove(2)
    if 5 in l:
      l.remove(5)
      
    if len(l) > 0:
      return 2
    else:
      return 1
    
def getGcd(a, b):
    if b == 0:
        return a
    return getGcd(b, a%b)

 

0. a/b가 유한소수면 1, 무한소수면 2

1. a/b가 정수면 유한소수로 분류

2. a/b의 기약분수 중 분모의 소인수가 2, 5만 존재해야 유한소수이므로 분자는 필요없다.

3. a, b의 gcd 구하고

4. 기약분수의 분모 target = b // gcd(a, b)

5. target의 소인수 구하고 set을 통해 중복 제거

6. 2, 5가 있을 경우 제거하고 남아있는 소인수가 있다면 무한소수, 없다면 유한소수

 

위 과정을 거쳐 풀었다.

 

다른 풀이

def solution(a, b):
    b //= getGcd(a,b)
    while b%2==0:
        b//=2
    while b%5==0:
        b//=5
    return 1 if b==1 else 2
    
def getGcd(a, b):
    if b == 0:
        return a
    return getGcd(b, a%b)

이렇게 깔끔하게 풀고 싶었는데

지금 보면

나랑 똑같이 일단 target 분모를 구한 다음 따로 소인수들을 구하지 않고

2와 5에 대해 모두 나눠줘서

남은 target이 1이면 유한소수, 아니면 무한소수가 되게끔 만들었다.