알고리즘 문제 연습

[프로그래머스,Java] 최대공약수와 최대공배수(유클리드 호제법)

codi-3 2024. 7. 29. 16:00

이문제를 풀기 위해 유클리드 호제법을 사용했다.

유클리드 호제법의 따르면 최대 공약수(Greatest Common Divisor): 

  • 임의의 다른 두 자연수 Max & Min 가존제하고 Max> Min 일 때
  • Max / Min의 나머지 값 즉 Max % Min을 R(remainder) 로정의하고
  • 그 과정을 Min = 0 이 될 때까지 반복하며 Max와 Min 값을 업데이트해 준다
  • Min = Max로 먼저 업데이트되며 Min = 나머지 값 R(remainder)로 업데이트해 준다.

최대공배수 (Greatest Common Multiple) 을구할때에는:

  • 두자연수 Max와 Min 을곱한값을 위에 계산한 최소공약수로 나누어준다. (Max * Min) / GCD(Max, Min).


✏️작성 코드

  • Min과 Max의 값을 Math.min 과 Math.max를 사용하여 정의 한뒤 위의 공식을 While반복문을 사용하여 풀어보았다.
class Solution {
    public int[] solution(int n, int m) {
        int[] answer = {n,m};
        int min = Math.min(n, m);;
        int max =Math.max(n,m);
        
        
        //유클리드 호재
        while(min != 0){
            int r = max % min;
            max = min;
            min = r;
        }

        
        answer[0] = max;
        answer[1] = (n * m) / max;
        return answer;
    }
}

 

이번문제는 어려운 문제는 아니었지만, 유클리드 호제법을 잘 알지 못한 상태였다면 난감했을 것 같다. 처음 문제를 봤을 때 어떤 로직을 사용할지 애를 먹었는데 구글링으로 유클리드 호제법을 찾아서 구현해 보니 쉽게 풀 수 있었다. 앞으로 나올 문제들 중 최대 공약수와 공배수가 적용되는 문제에 유용하게 사용할수있슬꺼같다.