[Python] 프로그래머스 : 최대공약수와 최소공배수

[문제 풀기 전 생각한 부분]

 

1. 최대 공약수는 어떻게 구할까?

# 더 큰 수에서 작은 수로 나누었을 때, 나누어 떨어 지는 경우 작은 수가 최대공약수이다.
# 두 수를 나누었을 때, 나누어 떨어지지 않는 다면 
# 두 수의 약수를 구한 뒤
# 두 수의 약수 중 같은 숫자를 고른다.
# 같은 숫자 중 가장 큰 수를 반환한다.

2. 최소공배수는 어떻게 구할까?

# 최소 공배수 구하는 방법
# 두 수 중 더 큰 수를 작은 수로 나누었을 때, 안 나눠지는 경우
# 두 수를 곱하는 수가 최소 공배수이다. 
# 두 수를 나누었을 때, 나누어진다면, 더 큰 수가 최소 공배수가 된다.
# 두 수를 각각 무한히 곱했을 때, 나오는 수 중 가장 작은 수가 최소 공배수이다.

[my_code]

 

1. 최대공약수

n = 124
m = 24

bigger_num = max(n,m)
smaller_num = min(n,m)

bigger_num_list = []
smaller_num_list = []

result = []

if bigger_num % smaller_num ==0:
    print(f"두 수의 최대공약수는 {smaller_num}입니다.")
else:
    for i in range(1,bigger_num):
        if bigger_num % i == 0:
            bigger_num_list.append(i)
            print(f"bigger_num_list : {bigger_num_list}")
    
    for i in range(1,smaller_num):
        if smaller_num % i == 0:
            smaller_num_list.append(i)
            print(f"smaller_num_list : {smaller_num_list}")
    
    final_result = [nums for nums in bigger_num_list if nums in smaller_num_list]

    result.append(max(final_result))

2. 최소공배수

if bigger_num % smaller_num == 0:
    result.append(bigger_num)
else:
    big_num = bigger_num
    small_num = smaller_num
    numbers = 1
    while big_num % small_num != 0:
        big_num = bigger_num * numbers
        small_num = smaller_num * numbers
        numbers += 1
    result.append(big_num)

print(result)

[문제점]

 

1. 최대공약수에서는 스파게티 코드지만 "구현"은 했다.

2. 최소공배수에서 big_num과 small_num 에 같은 numbers를 곱하게 되면 절대로 두 수는 같지 않을 것이다. 

[문제점 해결]

 

1. 코드가 너무 방대하고 가독성이 떨어져 다시 처음부터 짜기로 했다. 

def solution(n, m):
    result = []

    for i in range(min(n,m),0,-1):
        if n % i == 0 and m % i ==0:
            result.append(i)
            break

    for i in range(max(n,m),(n*m)+1):
        if i % n == 0 and i % m == 0:
            result.append(i)
            break
            
    return (result)

- 첫 번째 for 문은 최대공약수 구하는 함수이다.

    - n과 m 중 더 작은 수를 1~작은 수 까지 역순으로 넣어 둘 다 만족하는 i 가 나오면 break를 한다.

        - 원래는 result = [ ] 배열에 if 문을 만족하는 i 를 다 넣어 max_result = max(result) 하려고 했으나, 역순과 break 단축   

- 두 번째 for 문은 최소공배수 구하는 함수이다.

    - 최소 공배수는 두 정수 중 더 큰 수부터 두 수의 곱까지 범위를 정했다.