𝝅번째 알파카의 개발 낙서장

screen

[프로그래머스 / JAVA] Level 1 최대공약수와 최소공배수 (12940)

posts

알고리즘

시리즈 톺아보기

프로그래머스

프로그래머스
count

최대공약수와 최소공배수 🔗

랭크 사용 언어
Level 1 JAVA

🔗 최대공약수와 최소공배수

문제 설명 🔗

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, 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]을 리턴해야 합니다.

풀이 🔗

두 수 n, m의 최대공약수와 최소공배수를 구하는 문제. 최대공약수만 구하면 nm, 최대공약수를 활용해 최소공배수를 구할 수 있다.

약수를 일일히 구해 비교하는 방법도 있지만, 유클리드 호제법을 활용하여 최대공약수를 쉽게 구할 수 있다.


유클리드 호제법

  1. nm으로 나눠 나머지 r를 구한다.
    • r이 0일 경우, 나눴던 그 수가 최대공약수가 된다.
  2. nm으로, mr로 할당하여 1을 반복한다.

이렇게 최대공약수를 구하면, 최소공배수는 간단하게 구할 수 있다.

nm을 곱하고, 최대공약수로 이를 나누면 된다.


구한 두 값을 배열로 만들어 반환하면 된다.

코드 🔗

JAVA

0/**
1 * 최대공약수와 최소공배수 클래스
2 *
3 * @author RWB
4 * @since 2021.12.13 Mon 19:33:08
5 */
6class Solution
7{
8 /**
9 * 해답 반환 메서드
10 *
11 * @param n: [int] 정수 1
12 * @param m: [int] 정수 2
13 *
14 * @return [int[]] 해답
15 */
16 public int[] solution(int n, int m)
17 {
18 int[] answer = new int[2];
19
20 answer[0] = gcd(n, m);
21 answer[1] = n * m / answer[0];
22
23 return answer;
24 }
25
26 /**
27 * 유클리드 호제법 연산결과 반환 메서드
28 *
29 * @param n: [int] 정수 1
30 * @param m: [int] 정수 2
31 *
32 * @return [int] 최대공약수
33 */
34 private int gcd(int n, int m)
35 {
36 while (m != 0)
37 {
38 int r = n % m;
39
40 n = m;
41 m = r;
42 }
43
44 return n;
45 }
46}