https://school.programmers.co.kr/learn/courses/30/lessons/12953
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
소인수분해를 이용해서 문제를 풀었는데 시간 초과가 되었다..
나무 위키에서 최소 공배수에 관한 내용을 읽다보니
https://namu.wiki/w/%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98
최소공배수 - 나무위키
예시로 두 수 10, 12의 공배수를 찾고 싶다고 하자. 먼저 두 수의 배수를 쭉 나열한다. 10: 10, 20, 30, 40, 50, 60, 70, ... 12: 12, 24, 36, 48, 60, 72, ... 여기서 위아랫줄 동시에 나타나는 수가 바로 공배수이다.
namu.wiki
최대공약수(gcd)를 이용하는 방법도 있더라..
import java.util.*;
class Solution {
public int solution(int[] arr) {
int answer = arr[0];
if (arr.length == 1) return answer;
for (int i = 1; i < arr.length; i++) {
answer = lcm(answer, arr[i]);
}
return answer;
}
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
int gcd(int a, int b) {
int gt = a > b ? a : b;
int lt = a > b ? b : a;
int rest = gt % lt;
if (rest == 0) {
return lt;
}
return gcd(lt, rest);
}
}
사실상 수학 문제인가..?
