프로그래머스 문제 12 - Java 최대공약수와 최소공배수

코딩테스트 연습 - 최대공약수와 최소공배수 | 프로그래머스 (programmers.co.kr)

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

 

최대공약수와 최소공배수

문제 설명

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, 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 temp = (n < m) ? n : m; // m이 더 클경우 작은숫자는 n 아닐경우 m
        int[] answer = new int[2];
        for(int i = 1; i <= temp; i++)
            if(n % i == 0 && m % i ==0) // 최대공약수는 둘다 같은숫자로 떨어지는 숫자임
                answer[0] = i;
        answer[1] = n * m / answer[0];
        return answer;
    }
}

우선 temp 라는걸 만들어서 어떤숫자가 더 작은지 확인한다.

그 작은 숫자만큼 for문을 돌려서 1부터 작은 숫자까지 돌려서 나눠떨어지는 숫자를 찾는다.

만약 없을경우엔 제일 작은 숫자인 1이 될것이다.. (1은 무조건 나눠떨어지니까)

answer[1] (최소공배수) = 두 수의 곱 / 최대공약수

 

그 이후 조건에 맞게 answer[0]에는 최대공약수, answer[1]에는 최소공배수를 넣어준다.

 

실행 결과

채점을 시작합니다.

정확성 테스트

테스트 1 〉	통과 (0.02ms, 81MB)
테스트 2 〉	통과 (0.02ms, 77.6MB)
테스트 3 〉	통과 (0.01ms, 72.9MB)
테스트 4 〉	통과 (0.02ms, 73.2MB)
테스트 5 〉	통과 (0.02ms, 77.6MB)
테스트 6 〉	통과 (0.02ms, 72MB)
테스트 7 〉	통과 (0.02ms, 76.7MB)
테스트 8 〉	통과 (0.02ms, 85.1MB)
테스트 9 〉	통과 (0.02ms, 73.5MB)
테스트 10 〉	통과 (0.02ms, 72.5MB)
테스트 11 〉	통과 (0.04ms, 73MB)
테스트 12 〉	통과 (0.04ms, 86.3MB)
테스트 13 〉	통과 (0.04ms, 75.2MB)
테스트 14 〉	통과 (0.05ms, 77.9MB)
테스트 15 〉	통과 (0.03ms, 79.2MB)
테스트 16 〉	통과 (0.04ms, 81MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0