[99club/TIL] 6주차 - 월요일 TIL(Today I Learned)

항해99/99club1기TIL

[99club/TIL] 6주차 - 월요일 TIL(Today I Learned)

delay100 2024. 4. 29. 23:45

728x90

SMALL

안녕하세요. delay100 입니다!

미들러 문제

1번. N개의 최소공배수

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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

이 문제는 유클리드 호제법을 사용하면 됩니다.

~~그러나 필자는 유클리드 호제법에 대해 말만 들어봤지 실제로는 잘 몰랐습니다.~~

그래서 유클리드 호제법을 먼저 검색해보았고, 최대 공약수(+ 최소공배수)를 구해야하는 문제에서 쓰는 방식인 것을 알게 되었습니다.

유클리드 호제법은 최대 공약수를 구할때 쓰는데, 이렇게 구한 최대 공약수로 최소공배수까지 구할 수 있습니다.

최대 공약수(gcd)를 구한 후에 최소 공배수(lcm)를 구해줍니다.

먼저, 최대공약수를 구해줍니다.

최대공약수 = 2개의 숫자(a, b)를 나눴을 때 0이 되는 숫자

만약, 2개의 숫자를 나눴을 때 0이 되지 않는다면 나눈수(b)와 2개의 숫자를 나눈 값의 "나머지"를 가지고 또 한번 계산해줍니다. 나머지가 0이 될 때까지 계속 반복해주고, 나머지가 0이될 때 몫을 반환해줍니다.

다음으로 최소공배수를 구해줍니다.

최소공배수 = 2개의 숫자(a, b)를 곱하고 최대공약수로 나눈 숫자

그리고 다음 arr[i]에 가기 전에 a값을 최소공배수로 바꿔줍니다. 그럼 계속해서 현재까지의 최소공배수가 만들어집니다.

class Solution {
    public int solution(int[] arr) {
        int a = arr[0];
        int lcm = arr[0];
        
        for(int i=1; i<arr.length; i++) {
            lcm = a*arr[i]/gcd(a, arr[i]);
            a = lcm;
        }
        
        return lcm;
    }

    // 최대 공약수 구하기 -> 유클리드 호제법
    public static int gcd(int a, int b) {
        if(a % b == 0) {
            return b;
        }
        return gcd(b, a%b);
    }
}