[프로그래머스] 최대공약수와 최소공배수

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

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

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

---

Think🤔

두 개의 파라미터 값을 받아서 정수형 배열로 최대공약수와 최소공배수를 return하는 문제이다.

최대 공약수는 더 낮은 값에서 둘다 나뉘어 1부터 비교해서 나눠 떨어지면 최대 공약수가 나온다.

최소 공배수가 좀 어렵다..

구하는 방법은 아는데 막상 알고리즘으로 풀려고 하니 생각이 안난다... 흠....

 

구하는 방법을 식으로 적어보니

둘을 동시에 나누면서 그 값이 이제 동시에 나눠지지 않을때 각각 값이 남는데 그 값을 "서로소"라고 하고 그 서로소 두개를 곱해주면 최소 공배수가 된다.

 

그럼 이제 동시에 나누는 방법을 적용한다.

생각해보면 이미 서로소를 구하는 방법은 쉽다. 아까 구했던 최대 공약수로 각각 n과 m값을 나눠주면 서로소 값이 나온다.

---

Solution✍

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        
        // 둘 중 더 작은거까지 조사
        int small = Math.min(n,m);
        //최대공약수
        for(int i=1; i<=small; i++){
            if(n%i == 0 && m%i == 0){
                answer[0] = i;
            }
        }
        
        //최소공배수
        n = n/answer[0];
        m = m/answer[0];
        answer[1] = n * m * answer[0];
        return answer;
    }
}

마지막 최소 공배수를 구한 부분을 살짝 줄여보자면

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        
        // 둘 중 더 작은거까지 조사
        int small = Math.min(n,m);
        //최대공약수
        for(int i=1; i<=small; i++){
            if(n%i == 0 && m%i == 0){
                answer[0] = i;
            }
        }
        
        answer[1] = (n * m) / answer[0];
        return answer;
    }
}

---

Review🤩

재귀 함수적으로 짜는 코드법을 보았다.

static을 이용해서 새 메서드를 만들어서 재귀적으로 짜는 방법.. (다른 사람 코드)

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        answer[0] = gcd(n,m);
        answer[1] = (n*m)/answer[0];
        return answer;
    }
    public static int gcd(int p, int q){
        if (q==0) return p;
        return gcd(q, p%q);
    }
}

wow..

첫 번째 answer[0]에 최대 공약수를 넣어주는데 gcd라는 메서드를 먼저 생성한다.

p%q로 3을 12로 나눈 나머지는 0이 돼서 다시 gcd를 타는데 그러면 if 조건에 걸려서 3을 반환시킨다..

---