최대공약수와 최소공배수

Posted on Edited on In , ,

문제정의

두 수의 최대공약수와 최소공배수를 구하는 문제이다 두 수의 대소 관계는 정의되지 않았다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class BigDivSmallMul {

    //프로그래머스 문제 풀이 level1 최대공약수와 최소공배수
    public static void main(String[] args)
    {
        int n = 3, m = 12;
        int[] answer = new int[2];
        int min, max;
        min = Math.min(n, m);
        max = Math.max(n, m);
        int big_div = -2, small_mul = -2;
        for(int i = 1; i <= min; i++)
        {
            if(min%i == 0 && max%i == 0)
                big_div = i;
        }
        int temp = max;
        while(true)
        {
            if(temp % min == 0 && temp % max == 0)
            {
                small_mul = temp;
                break;
            }
            temp++;
        }
        answer[0] = big_div;
        answer[1] = small_mul;
    }
    
    
}
부분부분 보도록 하자 
1
2
3
4
5
6
7
8
9
10
11
int n = 3, m = 12;
int[] answer = new int[2];
int min, max;
min = Math.min(n, m);
max = Math.max(n, m);
int big_div = -2, small_mul = -2;
for(int i = 1; i <= min; i++)
{
    if(min%i == 0 && max%i == 0)
        big_div = i;
}
n과 m중에 크고 작은 값을 각각 min, max에 담았다. 최대공약수는 min값보다 클 수 없으므로 1에서 min까지 보면서 나눌 수 있는 최대를 big_div에 담는다. 여기서 n,m중 더 작은 값을 a라고 하면 시간복잡도는 \(O(a)\)로 볼 수 있다.

1
2
3
4
5
6
7
8
9
10
int temp = max;
while(true)
{
    if(temp % min == 0 && temp % max == 0)
    {
        small_mul = temp;
        break;
    }
    temp++;
}

최소공배수는 max값이상이어야 한다. temp값을 max로 한 뒤, temp를 증가하면서 처음으로 나누어떨어지는 수가 있으면 최소공배수 값을 업데이트하고 반복문을 탈출한다. 이 부분에서도 시간복잡도는 \(O(a)\)라는 것을 알 수 있다. 왜냐하면 최소공배수가 가장 큰 경우가 n*m이기 때문이다. 따라서 총 알고리즘의 시간복잡도는 \(O(a)\) \(a = min(n,m)\)이다.

테스트