[Study] 프로그래머스 lv.1 최대공약수와 최소공배수(76%)

풀이 로직

1. 두 수 중 큰 것을 m, 작은 것을 n으로 세팅해둔다
2. 1부터 n까지 증가시키며 최대공약수를 점검한다.
   2-1. 최대 공약수 : 그 수로 m과 n을 나누었을 때 나머지가 0인 수 중 가장 큰 수
3. 두 수의 곱 = 최대공약수 * 최소공배수 를 이용하여 최소 공배수를 구한다

내가 작성한 코드

class Solution {
    public int[] solution(int n, int m) {
        
        if (n > m){
            int temp = n;
            n = m;
            m = temp;
        }
        
        int divisor = 1;
                      
        for(int i = 1; i <= n ; i++){ // 최대 공약수 구하기
            if(m % i ==0 && n % i ==0){
                divisor = i;
            }
        }
        
        int multiple = m*n / divisor; // 두 수의 곱 = 최대공약수 * 최소공배수
        
        int[] answer = {divisor, multiple};
        return answer;
    }  
}

수행 시간

0.02ms ~ 0.11ms

테스트 1 〉	통과 (0.02ms, 72.9MB)
테스트 2 〉	통과 (0.02ms, 77.4MB)
테스트 3 〉	통과 (0.02ms, 79.2MB)
테스트 4 〉	통과 (0.02ms, 69.6MB)
테스트 5 〉	통과 (0.02ms, 74.9MB)
테스트 6 〉	통과 (0.02ms, 86.6MB)
테스트 7 〉	통과 (0.02ms, 78.5MB)
테스트 8 〉	통과 (0.02ms, 74.9MB)
테스트 9 〉	통과 (0.02ms, 77.5MB)
테스트 10 〉	통과 (0.03ms, 73.9MB)
테스트 11 〉	통과 (0.04ms, 71.8MB)
테스트 12 〉	통과 (0.11ms, 73.4MB)
테스트 13 〉	통과 (0.06ms, 76.4MB)
테스트 14 〉	통과 (0.07ms, 73.4MB)
테스트 15 〉	통과 (0.03ms, 65.8MB)
테스트 16 〉	통과 (0.05ms, 74.8MB)

다른 사람의 코드에서 배운 점

재귀 호출

함수의 두 인자를 맞바꿀 때 아래와 같이 재귀 호출을 수행할 수 있다

if(n > m) return solution(m, n);

내가 작성한 코드

        if (n > m){
            int temp = n;
            n = m;
            m = temp;
        }

유클리드 호제법을 사용한 풀이

유클리드 호제법
1071과 1029의 최대공약수를 구하면,
1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다.
≫ 42
1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다.
≫ 21
42는 21로 나누어 떨어진다.
따라서, 최대공약수는 21이다.

오늘 발표를 맡으신 팀원님 자료!

      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);
   }

1. 입력으로 두 수 m,n(m>n)이 들어온다.
2. n이 0이라면, m을 출력하고 알고리즘을 종료한다.
3. m이 n으로 나누어 떨어지면, n을 출력하고 알고리즘을 종료한다.
4. 그렇지 않으면, m을 n으로 나눈 나머지를 새롭게 m에 대입하고, m과 n을 바꾸고 3번으로 돌아온다.

만약 큰 수 두 개가 소수라면?

1) 소수 판별 메소드를 사용

최대공약수, 최소공배수를 구할 수 있다.

2) 유클리드 호제법 사용

루프를 큰 수부터 작은 수까지 쭉 돌 필요가 없어 통과 시간이 더 줄어든다.