logo

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

screen

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

posts

알고리즘

시리즈 톺아보기

프로그래머스

프로그래머스

Table of Contents

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의 최대공약수와 최소공배수를 구하는 문제. 최대공약수만 구하면 n과 m, 최대공약수를 활용해 최소공배수를 구할 수 있다.

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


유클리드 호제법

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

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

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


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

코드 🔗

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}

📆 작성일

2021-12-18 Sat 12:30:56

📚 카테고리

알고리즘알고리즘

🏷️ 태그

프로그래머스

알고리즘

JAVA(자바)

Level 1