[Java] 최대공약수와 최소공배수 (백준 2609번)

📖문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

• 첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.
• 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

---

✏️내 풀이

첫 번째 방법 -> 실패
두 번째 방법 -> 80ms
세 번째 방법 -> 76ms

첫 번째 방법

1. 입력값을 spilt을 사용해서 공백을 기준으로 구분한다.
2. 두 수를 나눈 나머지가 0이면 나눈 수를 누적곱한다. (=최소공배수)
3. 나눈 수<나누려는 수가 true일 때까지 반복한다.
4. 조건이 false가 되면 나누려는 수를 곱한다. (=최대공약수)
5. 최대공약수와 최소공배수를 출력한다.

package lv_1;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class B2609 {

	public static void main(String[] args) throws Exception{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		//입력값을 공백으로 나누어서 배열에 저장
		String [] arr = br.readLine().split(" ");

		//두 값을 각각의 변수에 저장
		int num1 = Integer.parseInt(arr[0]);
		int num2 = Integer.parseInt(arr[1]);

		int i = 2; //나누는 수
		int least = 1; //최소공배수
		int greatest = 1; //최대공약수

		//나눈 수(i) < 나누려는 수(num) 이면 반복
		while(i<=num1 && i<=num2) {

			//나머지가 0이면
			if(num1%i==0 && num2%i==0) {

				//값 = 몫
				num1 = num1/i;
				num2 = num2/i;

				//누적곱 (최대공약수)
				greatest *= i;

				i++;

			}else {

				//나머지가 0이 아니면 i값 초기화
				i = 2;
			}
		}

		//최소공배수
		least = greatest * num1 * num2;

		System.out.println(greatest); //최대공약수
		System.out.println(least); //최소공배수

	}

}

나름 그래도 생각한대로 잘 풀었다고 생각했는데.. 시간초과 뜸

두 번째 방법

1. 입력값을 spilt을 사용해서 공백을 기준으로 구분한다.
2. 두 수 중에 작은 수를 구한다.
3. 작은 수를 나눈 나머지가 0인 몫을 구한다.
   -> 이때 i=1부터 반복문을 시작해서 나머지가 0인 가장 큰 몫을 구한다.
4. 그 몫으로 큰 수를 나누고, 나머지가 0이면 그 수가 최대공약수이다.
5. 각 수를 최대공약수로 나누었을 때의 몫과 최대공약수를 곱하면 최소공배수가 된다.

package lv_1;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class B2609 {

	public static void main(String[] args) throws Exception{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		//입력값을 공백으로 나누어서 배열에 저장
		String [] arr = br.readLine().split(" ");

		//두 값을 각각의 변수에 저장
		int num1 = Integer.parseInt(arr[0]);
		int num2 = Integer.parseInt(arr[1]);

		int tmp; //값 비교를 위한 임시 변수

		//num1 < num2가 되도록 한다.
		if(num1>num2) {
			tmp = num1;
			num1 = num2;
			num2 = tmp;
		}

		int i = 1; //나누는 수
		int least = 1; //최소공배수
		int greatest = 1; //최대공약수

		//나누는 수가 num1보다 작거나 같을 때까지 반복
		while(i<=num1) {

			//num1을 나눈 나머지가 0인 가장 큰 몫을 구한다.
			if(num1%i == 0) {

				//그 몫으로 num2를 나누었을 때 나머지가 0이면
				if(num2%(num1/i) == 0) {

					//최대공약수는 그 몫이다.
					greatest *= (num1/i);

					//최소공배수를 구하기 위해, 각 수를 최대공약수로 나눈다.
					num1 /= greatest;
					num2 /= greatest;

					//반복문을 빠져나온다.
					break;
				}
			}
			i++;
		}

		//최소공배수
		least = greatest * num1 * num2;

		System.out.println(greatest);
		System.out.println(least);
	}
}

두번 실패 후 세번째 시도만에 성공..! 검색 없이 혼자서 풀고, 이전 두 문제들보다 시간도 짧게 걸려서 나름 뿌듯..😎

세 번째 방법

1. 입력값을 spilt을 사용해서 공백을 기준으로 구분한다.
2. 두 수 중에 작은 수를 구한다.
3. 반복문을 사용해서 두 수를 나누었을 때 나머지가 0인 몫 중에 가장 큰 값을 구한다.
4. 그 값이 최대공약수이다.
5. 두 수를 곱한 값을 최대공약수로 나누면 최소공배수가 된다.

package lv_1;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class B2609 {

	public static void main(String[] args) throws Exception{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		//입력값을 공백으로 나누어서 배열에 저장
		String [] arr = br.readLine().split(" ");

		//두 값을 각각의 변수에 저장
		int num1 = Integer.parseInt(arr[0]);
		int num2 = Integer.parseInt(arr[1]);

		int tmp; //값 비교를 위한 임시 변수

		//num1 < num2가 되도록 한다.
		if(num1>num2) {
			tmp = num1;
			num1 = num2;
			num2 = tmp;
		}

		int greatest = 1;

		//나누는 수가 num1보다 작거나 같을 때까지 반복
		for(int i=1;i<=num1;i++) {

			//num1 나머지가 0이고, num2 나머지도 0이면
			if(num1%i==0 && num2%i==0) {

				//최대공약수는 그 몫(i)이다.
				greatest = i;
			}
		}

		//최소공배수는 두 수를 곱한 값을 최대공약수로 나누면 된다.
		int least = num1 * num2 / greatest;

		System.out.println(greatest);
		System.out.println(least);
	}
}

다른 사람들 코드 보다가 발견해서 적용해봄. 처음에 i<num1이라고 해서 에러났는데 i<=num1로 바꾸니까 성공!
= 하나가 중요하다..