가장 크게 나눌 수 있는 공통 묶음 크기
자바스크립트 코딩테스트 문제로 gcd 주제를 연습해보세요. 난이도는 easy이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
여러 창고의 상품 개수를 모두 같은 크기 묶음으로 나누려고 할 때, 가능한 가장 큰 묶음 크기를 구하세요.
문제 설명
정수 배열 bundles가 주어집니다. bundles[i]는 i번째 창고에 있는 상품 개수입니다.
모든 창고의 상품을 같은 크기의 묶음으로 나누되, 각 창고에 남는 상품이 없어야 합니다. 이때 사용할 수 있는 묶음 크기 중 가장 큰 값을 반환하는 함수 largestCommonBundleSize를 작성하세요.
예를 들어 상품 개수가 [12, 18, 30]이라면 6개씩 묶을 수 있고, 7개씩은 모든 창고를 남김없이 나눌 수 없습니다. 따라서 정답은 6입니다.
제한사항
1 <= bundles.length <= 10,0000 <= bundles[i] <= 1,000,000,000bundles에는 적어도 하나 이상의 양수가 들어 있습니다.- 반환값은 모든 상품 개수를 남김없이 나눌 수 있는 가장 큰 양의 정수입니다.
예시
- 입력:
[12, 18, 30]-> 출력:6 - 입력:
[7, 13, 29]-> 출력:1 - 입력:
[24, 24, 24]-> 출력:24 - 입력:
[0, 10, 20]-> 출력:10
힌트
- 두 수를 모두 나눌 수 있는 가장 큰 수는 최대공약수입니다.
- 배열 전체의 답은 앞에서부터 최대공약수를 계속 누적하면 구할 수 있습니다.
gcd(0, x)는x로 처리할 수 있습니다.
해설
이 문제는 배열 전체의 최대공약수를 구하는 문제입니다. 어떤 묶음 크기 k가 모든 창고의 상품 개수를 남김없이 나누려면, k는 배열의 모든 값의 공약수여야 합니다. 가능한 묶음 크기 중 가장 큰 값은 결국 전체 배열의 최대공약수입니다.
최대공약수는 유클리드 호제법으로 빠르게 구할 수 있습니다. 두 수 a, b에 대해 gcd(a, b)는 b가 0이 될 때까지 gcd(b, a % b)로 바꾸어 계산합니다.
배열에서는 첫 값을 답 후보로 두고, 다음 값과의 최대공약수로 후보를 계속 갱신합니다. 중간에 0이 있어도 gcd(0, x) = x로 처리되므로 별도 예외 분기 없이 누적할 수 있습니다.
function largestCommonBundleSize(bundles) {
function gcd(a, b) {
a = Math.abs(a);
b = Math.abs(b);
while (b !== 0) {
const next = a % b;
a = b;
b = next;
}
return a;
}
let answer = 0;
for (const count of bundles) {
answer = gcd(answer, count);
}
return answer;
}
시간 복잡도는 O(n log M)입니다. 여기서 n은 배열 길이, M은 배열에서 가장 큰 값입니다. 추가 공간은 상수만 사용하므로 O(1)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.