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

About this offer

문제 소개 프로그래머스 Lv.1 · 최대공약수와 최소공배수 자연수 n과 m이 주어진다. 두 수의 최대공약수와 최소공배수를 구해 [최대공약수, 최소공배수] 배열로 반환하면 된다. 두 수는 모두 1 이상 1,000,000 이하다. 예를 들어 3과 12면 [3, 12] , 2와 5면 [1, 10] 을 반환한다. 접근 방법 최대공약수: 두 수 중 작은 쪽까지 1부터 차례로 나눠 본다. 두 수를 모두 나누어떨어지게 하는 수가 나올 때마다 answer[0] 을 갱신한다. 반복이 끝나면 마지막으로 저장된 값이 가장 큰 공약수다. 공약수는 작은 수보다 클 수 없으므로 작은 수까지만 확인한다. 최소공배수: 두 수의 곱 = 최대공약수 × 최소공배수 라는 성질을 이용한다. 그래서 n * m / 최대공약수 로 바로 구한다. 개선할 점도 두 가지 있다. 오버플로: n과 m이 최대 1,000,000이라 n * m 은 최대 1012까지 커진다. 이 값은 int 범위(약 21억)를 넘는다. 예를 들어 n=1,000,000, m=999,999면 최소공배수가 틀리게 나온다. (long) n * m / gcd 처럼 long으로 계산하거나, n / gcd * m 처럼 먼저 나누는 편이 안전하다. 유클리드 호제법: gcd(a, b) = gcd(b, a % b) 를 쓰면 최대공약수를 O(log min(n, m))에 구할 수 있다. 풀이 코드 class Solution { public int[] solution(int n, int m) { int[] answer = new int[2]; if(n < m) { for (int i = 1; i <= n; i++) { if(n % i == 0 && m % i == 0) { answer[0] = i; } } } else { for (int j = 1; j <= m; j++) { if(m % j == 0 && n % j == 0) { answer[0] = j; } } } answer[1] = n * m / answer[0]; return answer; } } 시간 복잡도 O(min(n, m)). 최대공약수를 찾을 때 1부터 두 수 중 작은 값까지 한 번씩 확인하기 때문이다.

Offer details

Provider

velog

Source

velog-rss

Score

54.39

Confidence

49%