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

최지나·2023년 10월 17일
2

코딩테스트

목록 보기
40/154

문제

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

제한 사항
두 수는 1이상 1000000이하의 자연수입니다.

입출력 예

nmreturn
312[3, 12]
25[1, 10]

문제 출처

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

생각

  • 최대공약수: 두 수중 더 작은 수부터 1까지 점점 줄여가면서 나누어 떨어지는지 확인 -> 나누어 떨어지는 순간 break;
  • 최소공배수: 두 수 중 더 큰 수부터 두 수의 곱까지 점점 숫자를 키워가면서 나누어 떨어지는지 확인 -> 나누어 떨어지는 순간 break;

코드

class Solution {
    public int[] solution(int n, int m) {
        
        int answer1 = 0;
        int answer2 = 0;
        for (int i = Math.min(n,m); i > 0; i--){
            if (n % i == 0 && m % i == 0){
                answer1 = i;
                break;
            }
        }
        for (int i = Math.max(n,m); i <= n*m ; i++){
            if (i % m == 0 && i % n == 0){
                answer2 = i;
                break;
            }
        }
        
        int[] answer = {answer1, answer2};
        return answer;
    }
}

다른 사람의 풀이

import java.util.Arrays;

class TryHelloWorld {
    public int[] gcdlcm(int a, int b) {
        int[] answer = new int[2];
        int standard = (a > b) ? a : b;

        for(int i=1; i<=standard; i++){
          if(a % i == 0 && b % i == 0) answer[0] = i;
        }
        answer[1] = (a * b) / answer[0];

        return answer;
    }
}

  • 최대공약수를 구하는 과정은 나의 풀이와 동일했으나, 최소공배수를 공식으로 푼 풀이를 가져왔다
    • 최소공배수 = 두 수의 곱 / 최대공약수
  • 문제를 풀 때 더 간단하게 풀 수 있는 방법을 조금 더 고민해야겠다,,,!!
profile
의견 나누는 것을 좋아합니다 ლ(・ヮ・ლ)

0개의 댓글