2021-06-16 / 최대공약수와 최소공배수

문제 설명

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

 

초기 코드

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = {};
        return answer;
    }
}

 

정답 코드

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];	//반환할 값은 최대공약수와 최소공배수 두개
        int small=n, big=m;
        if(n>m) {	//큰값까지 포문을 돌려야하기 때문
            small=m;
            big=n;
        }
        for(int i=1; i<big; i++){
            if(n%i==0 && m%i==0) answer[0]=i;
        }
        answer[1]=n*m/answer[0];
        return answer;
    }
}

 

코드 설명

최대공약수는 둘을 동시에 나눴을 때 나머지가 0인 수이다. 즉 같은 i값으로 나눴을 때 둘다 나머지가 없다면 공약수이다. 이때 포문 안에서 조건식을 주었기 때문에 i값은 점점 커지기 때문에 포문이 진행될수록 더 큰 최대공약수가 answer[0]에 들어간다.

최소공배수는 둘을 곱했을 때 최대공약수로 나눈 값이다. 둘을 공통으로 나눌 수 있는 수는 공약수이고, 최소를 구해야하기 때문에 제일 큰 공약수, 최대공약수로 나누는 것이다. 이때 최대공약수는 answer[0]에 저장되어 있다.

 

 

코딩테스트 연습 - 최대공약수와 최소공배수