https://school.programmers.co.kr/learn/courses/30/lessons/12953
문제 분류 : 코딩테스트 연습 > 연습문제 > N개의 최소공배수
난이도 : 2
문제 접근 1 (브루트 포스)
1부터 ~ 정답까지
class Solution {
public int solution(int[] arr) {
int answer = 1;
while(true){
boolean flag = true;
for(int target : arr){
if(answer % target !=0){
flag = false;
break;
}
}
if(flag) break;
answer++;
}
return answer;
}
}
arr의 길이도 최대 15이고 arr의 원소가 100이하여서 시간초과는 발생하지 않는다.
문제 접근 2 (GCD, LCM 활용)
GCD : 최대 공약수
LCM : 최소 공배수
A와 B가 있다.
A * B = GCD * LCM 이라는 공식이 있다.
GCD (최대 공약수는 재귀를 통해서 쉽게 구할 수 있다.)
public static int GCD(int a, int b){
if(b == 0) return a;
return GCD(b, a % b);
}
1. A와 B 사이에서 GCD를 구한다.
2. A * B = GCD * LCM 이라는 공식을 이용해서 LCM 을 구한다. LCM = A * B / GCD
3. A를 LCM으로 갱신하고 다음 인덱스로 진행
4. 1번 2번 3번을 반복
class Solution {
public int solution(int[] arr) {
int start = arr[0];
for(int i = 1; i < arr.length; i++){
int target = arr[i];
start = (start * target) / GCD(start, target);
}
return start;
}
public static int GCD(int a, int b){
if(b == 0) return a;
return GCD(b, a % b);
}
}
테스트 케이스 6은 엄청난 차이를 보인다.
이 문제는 입력 범위가 작아서 접근 1번으로도 통과 하지만 입력값이 조금만 커져도 접근 1번으로는 통과 못한다.
'Algorithm > Programmers Java' 카테고리의 다른 글
Java 프로그래머스 게임 맵 최단거리 (0) | 2024.02.29 |
---|---|
Java 프로그래머스 최솟값 만들기 (0) | 2024.02.29 |
Java 프로그래머스 짝지어 제거하기 (0) | 2024.02.29 |
Java 프로그래머스 카카오프렌즈 컬러링북 (0) | 2024.02.28 |
Java 프로그래머스 연속된 부분 수열의 합 (2) | 2024.02.28 |