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

* 문제

programmers.co.kr/learn/courses/30/lessons/12940

코딩테스트 연습 - 최대공약수와 최소공배수

 

* 문제 풀이 

- 첫째, n과 m중 가장 작은 수를 찾는다.

- 둘째, 가장 작은 수부터 반복문을 사용해 -1씩해 n과 m을 나머지가 동시에 0이 되는 값이 최대 공약수이다.

- 셋째, n과 m을 곱해 시작 수를 설정한다.

- 마지막, n과 m으로 나눈 나머지가 동시에 0이 되는 값이 최소 공배수이다.

 

* 생각

- 최대공약수와 최소 공배수를 구하는 규칙을 찾는게 약간 어려웠다.

유클리드 호제법을 이용하면 최적화되게 구할 수 있는 것 같다.

이러한 문제 풀이능력이 쌓여서 고급 문제도 풀 수 있는 것 같다.

 

* 코드 

def solution(n, m):
    answer = []
    
    min_val = min(n, m)
    for i in range(min_val, 0, -1):
        if (n%i == 0) and (m%i == 0):
            answer.append(i)
            break
            
    max_val = n * m
    for i in range(min_val, max_val+1):
        if (i%n == 0) and (i%m == 0):
            answer.append(i)
            break
            
    return answer