본문 바로가기

개발

[알고리즘 문제] 최대공약수와 최소공배수



http://tryhelloworld.co.kr/challenge_codes/10


( 문제 ) Level1


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




( 구현 - 자바 )


TryHelloWorld.java


import java.util.Arrays;


class TryHelloWorld {

    public int[] gcdlcm(int a, int b) {

             

      int[] answer = new int[2];

int num1 = a;

        int num2 = b;

      int m = 1; // 몫

      

      // 큰수를 작은수로 나누기 위해 num1자리에 큰수 지정(스왑)

if(num1 < num2){

            int tmp = num1;

            num1 = num2;

            num2 = tmp;

        }        

      // 나머지가 0이 되는 순간 큰수가 최대공약수이다.

      while(m > 0){

          m = num1 % num2;

            num1 = num2;

           num2 = m;

        }

      answer[0] = num1;

      

// 처음 입력받은 두수의 곱을 최대공약수로 나누면 최소공배수가 된다.

      answer[1] = (a*b) / answer[0];

        return answer;

    }


    // 아래는 테스트로 출력해 보기 위한 코드입니다.

    public static void main(String[] args) {

        TryHelloWorld c = new TryHelloWorld();

        System.out.println(Arrays.toString(c.gcdlcm(3, 12)));

    }

}



( 결과 출력 )


[3, 12]


실행시간: 62ms






맨 위로