2026.03.31
문제 설명
두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.
제한 사항
- arr은 길이 1이상, 15이하인 배열입니다.
- arr의 원소는 100 이하인 자연수입니다.
입출력 예
문제 풀이
1차 실행 오류
9, 15와 같은 배열일 때의 경우의 수를 고려하지 않음
3을 공약수로 갖지만 배열에 3이 존재하지 않아서 나눠지지 않음
import java.util.Arrays;
class Solution {
public int solution(int[] arr) {
int answer = 1;
int dividedIndex = 0;
Arrays.sort(arr); // 오름차순 정렬
while(true) {
if (dividedIndex >= arr.length - 1) {
break;
}
for (int i = dividedIndex; i >= 0; i--) {
int n = dividedIndex + 1;
if (arr[n] % arr[i] == 0) {
arr[n] /= arr[i];
}
}
dividedIndex++;
}
for (int i = 0; i < arr.length; i++) {
answer *= arr[i];
}
return answer;
}
}2차 실행 오류
소인수를 구해야 하는데 약수를 구함
import java.util.Arrays;
import java.util.Map;
import java.util.HashMap;
class Solution {
public int solution(int[] arr) {
int answer = 1;
Map<Integer, Integer> map = new HashMap<>();
Map<Integer, Integer> tempMap = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
for (int j = 1; j <= arr[i] / 2; j++) {
if (arr[i] / j == 0) {
tempMap.put(j, tempMap.getOrDefault(j, 0) + 1);
}
}
for (Map.Entry<Integer, Integer> entry : tempMap.entrySet()) {
Integer n = map.get(entry.getKey());
if (n == null || n < entry.getValue()) {
map.put(entry.getKey(), entry.getValue());
}
}
}
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
answer *= Math.pow(entry.getKey(), entry.getValue());
}
return answer;
}
}나의 코드
소요 시간: 1시간 46분
제한 조건인 1~100에서 소수를 찾고,
각 수의 밑을 key, 지수를 value로 HashMap으로 임시 저장한 후,
현재 저장된 소인수의 지수보다 클 때만 교체하여 최소공배수를 찾는 방식을 사용했다.
간단히 최소공배수를 찾는 문제라 쉬울 줄 알았는데, 이를 알고리즘으로 표현하는 것이 생각보다 너무 어려웠다.
무엇보다 코드 알고리즘을 3번이나 바꾸면서 집중력이 떨어져서 효율이 잘 나오지 않아 1시간 46분이라는 긴 시간이 걸린 것 같다. 독서로 집중력을 높여야 하나?
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class Solution {
public int solution(int[] arr) {
int answer = 1;
List<Integer> primes = new ArrayList<>();
Map<Integer, Integer> map = new HashMap<>();
boolean isPrime = true;
for (int i = 2; i <= 100; i++) {
isPrime = true;
for (int j = 2; j <= i / 2; j++) {
if (i % j == 0) { isPrime = false; break; }
}
if (isPrime) { primes.add(i); }
}
for (int i = 0; i < arr.length; i++) {
Map<Integer, Integer> tempMap = new HashMap<>();
while(true) {
if (arr[i] == 1) { break; }
for (Integer p : primes) {
if (arr[i] < p) { break; }
if (arr[i] == p) {
tempMap.put(p, tempMap.getOrDefault(p, 0) + 1);
arr[i] = 1;
break;
}
if (arr[i] % p == 0) {
tempMap.put(p, tempMap.getOrDefault(p, 0) + 1);
arr[i] /= p;
break;
}
}
}
for (Map.Entry<Integer, Integer> entry : tempMap.entrySet()) {
int key = entry.getKey();
if (map.getOrDefault(key, 0) < entry.getValue()) {
map.put(key, entry.getValue());
}
}
}
for (Integer p : primes) {
if (map.get(p) == null) { continue; }
answer *= Math.pow(p, map.get(p));
}
return answer;
}
}AI 코드
유클리드 호제법: 두 수의 최대공약수(GCD)를 구하는 알고리즘
GCD(a, b) = GCD(b, a % b)
a % b == 0 이 되면 b가 최대공약수
GCD(48, 18) → 48 % 18 = 12
GCD(18, 12) → 18 % 12 = 6
GCD(12, 6) → 12 % 6 = 0
→ 최대공약수 = 6
두 수의 곱을 최대공약수로 나누면 최소공배수라는 수학적 공식을 이용하여
LCM(a, b) = a * b / GCD(a, b)
예시) LCM(48, 18)
= 48 * 18 / 6
= 144
class Solution {
public int solution(int[] arr) {
int answer = arr[0];
for (int i = 1; i < arr.length; i++) {
answer = lcm(answer, arr[i]);
}
return answer;
}
public int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
public int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
}