728x90
반응형
문제:
두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.
풀이 방법:
일단 최소공배수를 구하기 위해서 최대공약수(gcd)를 구하는 함수도 필요하다. 왜냐하면 최소공배수는 두 수의 곱을 최대공약수로 나눈 값과 같기 때문이다. N개의 최소공배수를 구하는 것도 크게 다르지 않다. N개가 있다면 그 중 계속 2개를 골라서 최소공배수를 구하고 그 값을 다시 arr 배열에 담는다. 이 과정을 arr의 원소가 1개가 남을 때까지 하면 그 남은 원소가 N개의 수들의 최소공배수가 되는 것이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 | def gcd(a,b): a,b=max(a,b),min(a,b) while b > 0: a,b=b,a%b return a def solution(arr): while len(arr) !=1: a=arr.pop() b=arr.pop() c=gcd(a,b) arr.insert(0,int(a*b/c)) answer=arr[0] return answer | cs |
728x90
반응형
'Algorithm > Python' 카테고리의 다른 글
| [Programmers]Lv 2.소수 만들기 (0) | 2019.03.26 |
|---|---|
| [Programmers]Lv 3.단어 변환 (0) | 2019.03.25 |
| [Programmers]Lv 3. 숫자 게임 (0) | 2019.03.23 |
| [Programmers]Lv 2.JadenCase 문자열 만들기 (0) | 2019.03.22 |
| [Programmers]Lv 3.짝지어 제거하기 (0) | 2019.03.21 |