최대공약수, 최소공배수(유클리드호제법)

https://programmers.co.kr/learn/courses/30/lessons/12940

코딩테스트 연습 - 최대공약수와 최소공배수

 

파이썬에도 풀어봤던 최대공약수, 최소공배수 문제인데, 유클리드의 호제법이 기억나지 않아 삽질하다가 결국 유클리드호제법을 찾아보고 풀었습니다. 기존 문제 풀이기법(1이 나올때까지 2부터 나눠서 나눠지면 그 수를 저장하는 방식)에 비해 용량이 3분의 2수준으로 줄었고 시간도 단축되서, 이 방식으로 푸는 게 맞다는 것을 깨달았습니다. 

// 내가 푼 풀이
package programmers;

public class 최대공약수와최소공배수 {
	public static void main(String[] args) {
		System.out.println(solution(2, 5)[0]+","+solution(2, 5)[1]);
	}
	public static int[] solution(int n, int m) {
        int max;// 큰 수 저장
        int min;// 작은 수 저장
        int remain;// 나머지 저장용
        int[] answer = new int[2];
        
        // 큰수, 작은 수 구분
        if(n>=m){
            max = n;
            min = m;
        }
        else{
            max = m;
            min = n;
        }
        
        //큰수가 작은 수의 배수면 바로 return
        if(max % min ==0){
            answer[0] = min;
            answer[1] = max;
        }
        // 아닐경우 유클리드호제법 사용 
        // a와 b의 최대공약수는 b와 a%b의 최대 공약수와 같다. a%b가 0이면 끝난것
        else{
        	while(max%min!=0) {
        		remain = max%min;
        		max = min;
        		min = remain;
        	}
        	answer[0] = min;
        	answer[1] = n*m/min;
        }
        return answer;
    }
}

 

// 다른 사람이 푼 풀이
import java.util.Arrays;

class TryHelloWorld {
    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) {
        TryHelloWorld c = new TryHelloWorld();
        System.out.println(Arrays.toString(c.gcdlcm(3, 12)));
    }
}

• 추천을 많이 받은 사람의 코드와 내 코드가 다른 점
  • 유클리드 호제법을 함수로 구현
  • 출력을 Arrays.toString(배열)로 설정: 배열내의 전체 요소의 정보 출력

아직도 부족함을 느끼는 부분은 기능을 함수화하는 것이 습관화되어있지 않다는 점입니다.
코드의 가독성을 위해서도 얼른 습관을 들여야겠다는 각오를 다시 한번 다져봅니다.