[파이썬][프로그래머스] 최대공약수와 최소공배수
1. 문제Permalink
[level 1] 최대공약수와 최소공배수 - 12940Permalink
성능 요약Permalink
메모리: 10 MB, 시간: 0.36 ms
구분Permalink
코딩테스트 연습 > 연습문제
채점결과Permalink
정확성: 100.0
합계: 100.0 / 100.0
문제 설명Permalink
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.
제한 사항
- 두 수는 1이상 1000000이하의 자연수입니다.
입출력 예
| n | m | return |
|---|---|---|
| 3 | 12 | [3, 12] |
| 2 | 5 | [1, 10] |
입출력 예 설명
입출력 예 #1
위의 설명과 같습니다.
입출력 예 #2
자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
2. 해결방법 시간복잡도Permalink
- 단순 코딩 O(NlogN)
3. 문제 해결 및 코드Permalink
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def solution(n, m): | |
| max = [] | |
| min = [] | |
| if n <= m: | |
| for i in range(1, n + 1): | |
| if n % i == 0 and m % i == 0: | |
| max.append(i) | |
| for j in range(1, m + 1): | |
| if (n * j) % m == 0: | |
| min.append(n * j) | |
| else: | |
| for i in range(1, m + 1): | |
| if m % i == 0 and n % i == 0: | |
| max.append(i) | |
| for j in range(1, n + 1): | |
| if (m * j) % n == 0: | |
| min.append(m * j) | |
| min = sorted(min) | |
| max = sorted(max) | |
| return [max[-1], min[0]] |
-
주석을 참고하면서 이해를 돕습니다.Permalink
4. 알고리즘 및 해설Permalink
- 두 값을 비교해서 큰 경우와 작은 경우를 만든다.
- 최대공약수와 최소공배수의 경우 나오는 값이 다르기때문에 이렇게 분리해준다.
- 반복문을 통해 두 값이 나누어서 0이 되는 경우와 해당 값이 아닌 값을 곱해서 해당 값과 나누어서 0이 되는 경우를 최소 공배수와 최대 공약수 리스트에 넣어준다.
- 이후 정렬하여 최대값과 최소값을 출력해준다.