백준 B1 2609 : 최대공약수와 최소공배수 🅾️

[문제]

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

2609번: 최대공약수와 최소공배수

 

[풀이]

첫 번째 코드

import java.io.*;

public class Main {
	
	public static int maxCal(int x, int y) {
		if(x<y) {
			int max=y;
			y=x;
			x=max;
		} else if(x==y) {
			System.out.println(x);
			System.out.println(x);
			return -1;
		}
		
		int z=x%y;
		while(z!=0) {
			int tmp=x%y;
			x=y;
			y=tmp;
			z=x%y;
		}
		
		return y;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String input=br.readLine();
		String[] inputArr=input.split(" ");
		
		int x=Integer.parseInt(inputArr[0]);
		int y=Integer.parseInt(inputArr[1]);
		
		int max=maxCal(x, y);
		if(max!=-1) {
			System.out.println(max);
			System.out.println((x/max)*y);
		}
	}

}

 

정석적인 방법으로 풀었다. while 반복문을 활용해서 최대공약수를 구한 뒤 max 변수에 값을 넣고,

최소공배수는 처음에 받은 x를 최대공약수로 나눈 값에 y를 곱해주면 끝.

결과는 아래와 같이 성공이다.

 

그리고 문득 재귀로 풀면 어떨까 싶어 재귀로도 풀어보았다.

 

두 번째 코드

import java.io.*;

public class Main {
	static int max;
	
	public static void maxCal(int x, int y) {
		if(x%y==0) return;
		max=x%y;
		maxCal(y, max);
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String input=br.readLine();
		String[] inputArr=input.split(" ");
		
		int x=Integer.parseInt(inputArr[0]);
		int y=Integer.parseInt(inputArr[1]);
		
		if(x<y) {
			int max=y;
			y=x;
			x=max;
		}
		
		if(x==y) {
			System.out.println(x+"\n"+x);
		} else {
			maxCal(x, y);
			System.out.println(max);
			System.out.println((x/max)*y);
		}
	}

}

 

단순히 반복문 대신 재귀로 메소드를 구현한 방법이다.

그러나 실수가 있었는지 아래 결과와 같이 런타임 에러가 발생했다.

 

무엇이 문제였는지 확인해보니, 만약 x%y가 처음부터 0인 경우 max가 0으로 초기화되어 (static 변수고 선언만 해준 상태라)

최대공약수가 자동으로 0이 되어버린다. 0으로 나누는 경우 java는 오류가 발생하기 때문에 런타임 에러가 발생했던 것이다.

아래 코드는 이 부분을 수정해준 코드이다.

 

세 번째 코드

import java.io.*;

public class Main {
	static int max;
	
	public static void maxCal(int x, int y) {
		if(x%y==0) return;
		max=x%y;
		maxCal(y, max);
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String input=br.readLine();
		String[] inputArr=input.split(" ");
		
		int x=Integer.parseInt(inputArr[0]);
		int y=Integer.parseInt(inputArr[1]);
		
		if(x<y) {
			int tmp=y;
			y=x;
			x=tmp;
		}
		
		if(x==y) {
			System.out.println(x+"\n"+x);
		} else {
			max=y;
			maxCal(x, y);
			System.out.println(max);
			System.out.println((x/max)*y);
		}
	}

}

 

결과는 아래와 같이 성공.

 

반복문과 결과를 비교해보면, 반복문이 30ms 정도 빠르다..

서버차이가 존재할 수는 있지만 어쨌든 둘 중 어떤 방법이 더 효율적이라고 말하기엔 애매한 결과이다.

애초에 코드도 반복문을 재귀로 그대로 바꾸기만 한 코드였기 때문에 예상은 했지만..^^

그래도 반복문보다 덜 익숙한 재귀 코드 작성을 연습했으니~ 좋은 경험이었다!