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

프로그래머스 Level 1 최대공약수와 최소공배수 (자바)

 

문제

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

 

제한사항

• 두 수는 1이상 1000000이하의 자연수입니다.

 

 

입출력 예

입출력 예

한 줄 요약

주어진 두 수의 최대공약수와 최소공배수를 구하기! 최대공약수와 최소공배수와의 관계를 활용해야 한다.

 

내 코드

1. 반환 수의 길이는 2로 고정이므로 answer 배열의 길이는 2로 지정한다.

2. n>m일 때와 n<m일 때로 나눠서 연산을 진행한다.

3. n과 m을 i로 나눴을 때 나머지가 0이면 그 수는 최대공약수가 된다. (i가 여러 개일 수 있지만 for문으로 제일 큰 i가 반환된다.)

    - 이 때, answer[0] = i(최대공약수)를 넣고 answer[1] = (m*n)/i를 넣는다. ((m*n)/i)가 최소공배수 구하는 연산이다.)

import java.util.*;

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        
        //최대공약수 구하는 법 ? -> 두 수의 최대로 나눌 수 있는 수
        //최소공배수 구하는 법 ? -> 두 수의 최대로 나눌 수 있는 수 * 나머지 2개
        if (n < m) {
                        
            for (int i=1; i<m; i++) {
                if (n%i == 0 && m%i == 0) {
                    answer[0]=i;
                    answer[1]=(m*n)/i;
                }
            }
        } else {
            
            for (int i=1; i<n; i++) {
                if (n%i == 0 && m%i == 0) {
                    answer[0]=i;
                    answer[1]=(m*n)/i;
                }
            }
        }
        
        return answer;
    }
}

 

최대공약수는 두 수를 나눴을 때 나머지가 0인 것과 최소공배수는 (두 수의 곱)/최대공약수 것이 핵심!