[프로그래머스/Lv.1] 최대공약수와 최소공배수

1. Input

1) 자연수 n

2) 자연수 m

 

2. Output

1) 두 수의 최대공약수와 최소공배수를 담은 배열

 

3. Constraint

1) n, m은 1 이상 1,000,000 이하의 자연수

 

4. Example

Input: n=3, m=12 -> Output: {3, 12}

 

5. Code

1) 첫 코드(2022/??)

int x, y;
if(n>m) {
    x = m; y = n;
}
else {
    x = n; y = m;
} // 둘 중 작은 수가 x, 큰 수가 y

int[] answer = {x, y}; // y가 x의 배수일때를 디폴트 값으로

if(y%x != 0) { // y가 x의 배수가 아닐 때 실행
    for(int i=x-1 ; i>0 ; i--) { // x-1부터 1씩 줄여가면서
        if( x%i==0 && y%i==0) { // 공약수를 찾으면
            answer[0] = i; // 처음 나오는 i값이 최대공약수
            answer[1] = x*y/i; // 두 수의 곱 = 최대공약수 * 최소공배수
            break;
        }   				
    } // for i
}
return answer;

2) 조금 더 간결하게 바꿔본 코드(2022/11/23)

int big = Math.max(n,m);
int small = Math.min(n,m);

int[] answer = {small, big}; // big이 small의 배수라고 가정
if(big%small!=0){
    for(int i=small-1 ; i>0 ; i--)
        if(big%i==0 && small%i==0){
            answer[0] = i;
            answer[1] = big/i*small; // 두 수의 곱 = 최대공약수 * 최소공배수
            break;
        }
}
return answer;

  - big*small*i 보다 big/i*small이 계산이 빨랐다.