본문 바로가기
코딩테스트/프로그래머스

[프로그래머스/java] 최대공약수와 최소공배수 구하기

by drCode 2020. 12. 14.
728x90
반응형

최대공약수와 최소공배수

문제 설명

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

 

package gcfLcm;

import java.util.Arrays;
import java.util.Scanner;

public class GcfLcm {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);

		Solution s = new Solution();

		System.out.println(Arrays.toString(s.solution(input.nextInt(), input.nextInt())));
	}
}

class Solution {
    public int[] solution(int n, int m) {
    	int max = 0;

    	for (int i = 2; i <= n; i++) {
			if(n % i == 0 && m % i == 0) {
				max = i;
			}
		}

    	if(max == 0) max = 1;

    	int min = m*n;

    	for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= m; j++) {
				if(n*j > m*i) break;
				if(n * j == m * i) {
					min = n*j;
					break;
				}
			}

			if(min != m*n) break;
		}

        int[] answer = {max, min};
        return answer;
    }
}

 

※ 어려웠던 점

(1) 쓸데 없이 n과 m의 약수 리스트를 구했었다.

(2) 최소 공배수는 m*n/max 로도 해결된다.

 

728x90
반응형

댓글