[프로그래머스] 최대공약수와 최소공배수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

2. 풀이과정

최대공약수는 각 수의 공약수들을 각 세트로 구한 뒤, 두 세트의 교집합 중 최댓값을 구하면 된다.

 

1. 각 공약수를 저장할 세트를 생성한다. Set1 = set()  Set2 = set()
2. 각 수를 나눠줄 변수를 생성하고 1로 초기화한다. i = 1
3. 원하는 지점에서 종료하기 위해 무한 반복문을 사용한다. while (True)
4. 입력받은 매개변수 n의 약수를 세트에 추가한다. if (n % i == 0): Set1.add(i)
5. 입력받은 매개변수 m의 약수를 세트에 추가한다. if (m % i == 0): Set2.add(i)
6. 만약 나누는 수가 두 수보다 크면 종료한다. if (n <= i and m <= i): break
7. 반복문이 종료되지 않았다면 나누는 수를 1 증가시켜 반복을 계속 진행한다. i += 1
8. 각 수의 약수를 모두 구했으면 두 약수 그룹의 교집합에서 최댓값을 최대공약수로 저장한다. answer.append(max(Set1 & Set2))
9. 1부터 두 수의 곱까지 수 중 최소공배수를 찾는다. for i in range(1, n * m + 1)
10. 만약 두 수의 배수이면 if (i % n == 0) and (i % m == 0)
11. 최소공배수로 저장한다. answer.append(i)
12. 최소공배수를 구했으니 반복을 종료한다. break

반응형

3. 소스코드

def solution(n, m):
    answer = []
    
    Set1 = set()
    Set2 = set()
    
    i = 1
    while (True):
        if (n % i == 0):
            Set1.add(i)
        if (m % i == 0):
            Set2.add(i)
            
        if (n <= i and m <= i):
            break
            
        i += 1
        
    answer.append(max(Set1 & Set2))
    
    for i in range(1, n * m + 1):
        if (i % n == 0) and (i % m == 0):
            answer.append(i)
            break
        
    return answer