1D1A - One Day One Algorithm

1D1A - One Day One Algorithm

최대공약수와 최소공배수

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

import java.util.Arrays;

import java.util.ArrayList;

import java.util.List;

class TryHelloWorld {

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

        int[] answer = new int[2];

        List<Integer> al = new ArrayList<>();

        List<Integer> bl = new ArrayList<>();

        for (int i=2; i<=a; i++) {

            if (a%i == 0) al.add(i);

        }

        for (int i=2; i<=b; i++) {

            if (b%i == 0) bl.add(i);

        }

        boolean setZero = false;

        for (int i = al.size(); i>0; i--) {

            for (int j= bl.size(); j>0; j--) {

                if (al.get(i-1).equals(bl.get(j-1))) {

                    answer[0] = al.get(i-1);

                    setZero = true;

                    break;

                }

            }

        }

        if (!setZero) {

            answer[0] = 1;

        }

        if (al.size() == 1 && bl.size() == 1) {

            answer[1] = a * b;

            return answer;

        }

        if (a>b) {

            if (a%b == 0) {

                answer[1] = a;

                return answer;

            }

        }

        else {

            if (b%a == 0) {

                answer[1] = b;

                return answer;

            }

        }

      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)));

    }

}

최소공배수는 어떻게 풀어야하는지 몰라서 참고했다.

모범답안

package com.company;

import java.util.Arrays;

public class Algorithm {

    public int[] gcdlcm(int a, int b) {
        int[] answer = new int[2];

        answer[0] = gcd(a, b);
        answer[1] = (a * b) / answer[0];
        return answer;
    }

    public static int gcd(int p, int q) {
        if (q == 0) return p;
        return gcd(q, p % q);
    }

    // 아래는 테스트로 출력해 보기 위한 코드입니다.
    public static void main(String[] args) {
        Algorithm c = new Algorithm();
        System.out.println(Arrays.toString(c.gcdlcm(3, 12)));
    }
}