[18/07/17] 프로그래머스- Level 1 최대 공약수와 최소 공배수

최대공약수와 최소공배수

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, 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]을 리턴해야 합니다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        List<Integer> nList = new ArrayList<>();
        List<Integer> mList = new ArrayList<>();
        List<Integer> list = new ArrayList<>();

        // 1. 두 수가 나누어 질 때
        if (m % n == 0 || n % m == 0) {
            // 최대공약수
            answer[0] = Math.min(m, n);
            // 최소공배수
            answer[1] = Math.max(m, n);
        }
        // 2. 두 수가 나누어 지지 않을 때
        else {

            // 최대공약수

      // n의 약수
          for (int i = 1; i <= n; i++) {
                           if (n % i == 0) {
                               nList.add(i);
                                  }
            }
            // m의 약수
          for (int i = 1; i <= m; i++) {
                        if (m % i == 0) {
                            mList.add(i);
                        }
            }

            // 공약수
            for (int i = 0; i < nList.size(); i++) {
                            for (int j = 0; j < mList.size(); j++) {
                                    if (nList.get(i).equals(mList.get(j))) {
                                            list.add(nList.get(i));
                                                }
                                                }
            }
            answer[0] = Collections.max(list);

            // 최소 공배수
            answer[1] = n / answer[0] * m;

        }
        return answer;
    }

}

정보처리기사 시험때 알고리즘 공부를 했는데 다 까먹었다. 유클리드 호제법으로 푼거 같은데 기억이 안난다...... 그래서 굉장히 비효율적인 알고리즘이라 보여진다. for문이 너무 많다.....

어쨌든 로직은 다음과 같다.

1. n과 m이 나누어질 때(서로 공약수 인 경우)는  작은수가 최대공약수, 큰수가 최소공배수이다.

2. 나누어 지지 않을 경우에는 일단 n과 m의 약수를 각각 구하고, 공약수를 찾은 다음 최대 공약수를 선택한다.

  이후 최소 공배수는 둘중 아무수나 최대 공약수로 나눈 다음 남은 아무 수중 안 나눈 수로 곱하면 최소 공배수가 된다.