수학적 원리를 이용하자.
첫번째로 작성한 코드가 모두 오류가 난 후 뭔가 힌트를 봐야만 하는 필요설을 느꼈다. 그래서 질문하기 찬스를 이용하였더니, 최소공배수와 최대공약수에 대한 수학적 특성을 이용하여 푸는 문제임을 알게 되었다.(사실 초등학교 언저리에서 배웠겠지만, 기억이...🥲)
-
최대공약수와 최소공배수란
최대공약수 = G 최소공배수 = L G | A B -------- a b → 최대공약수 : G → 최소공배수 : L = G * a * b이제부터가 진짜다!! 위 블락은 누구나(?) 기본적으로 알고 있는 부분일 것이다. 하지만 아래는
유클리드 호제법이라는 알고리즘에 대한 내용이다.(들어는 봤지만 기억하지 못하는 그것...) 유클리드 호제법은2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘이다.cf. 정식(整式) : 덧셈ㆍ뺄셈ㆍ곱셈만의 연산을 사용하여 얻어지는 대수식
-
최대공약수 구하는 방법
A와 B : 특정 수 A % B → 나머지(C) B % C → 나머지(D) C % D → 나머지(E) ... 두수가 나누어 떨어질 때까지 반복 나누어 떨어질 때, 나누는 수가 최대공약수 -
최소공배수 구하는 방법
A와 B : 특정 수 G는 최대공약수 / L은 최소공배수 A = G * a B = G * b (a와 b는 서로소 관계) 위에서 보면 L = G * a * b 이다 A * B = G * G * a * b → 양변을 G로 나눈다 A * B / G = G * a * b = L유클리드 호제법을 이용하여 최대공약수를 구하면 위에서 언급한 식을 통해서 최소공배수도 구할 수 있다.
수학적 특성을 이해한 후 다시 도전!
위에서 설명한 최소공배수와 최대공약수는 두 수 사이에서 일어나는 상황을 가정한 것이다. 그렇다면 여러 숫자 사이에서는 어떻게 될까? 두 수의 최소공배수를 구하고, 다시 그 최소공배수와 다음수와의 최소공배수를 구하고... 이런 식으로 반복하면 내가 원하는 최종적인 최소공배수를 구할 수 있다.
let lcm = 1;
for (let i = 0; i < arr.length; i++) {
let max = Math.max(arr[i], lcm);
let min = Math.min(arr[i], lcm);
while (true) {
if (max % min !== 0) [max, min] = [min, max % min];
else {
lcm = (lcm * arr[i]) / min;
break;
}
}
}
return lcm;Try1을 나중에 적은 이유는 아래 코드가 왜 안되는지를 나중에 알았기 때문이다. 아래 코드는 제출하면 모든 테스트 케이스에서 오류를 분출(?)한다. 이 코드는 왜 모든 케이스에서 오류가 났을까? 🤔 그 이유에 대해서 드디어 알게 되었다. 아래 이미지를 보자.
왼쪽 : 케이스1 | 오른쪽 : 케이스2
일반적으로 최소공배수를 구하는 경우 케이스1과 같은 작업을 통해서 구하게 된다. 그래서 나는 이런 경우만 가정하고 아래와 같은 코드를 구현하였다. 하지만 케이스2와 같은 경우는 어떻게 할까? 이미지에서도 적어놨지만, 두 수의 최소공배수를 구하고, 그 최소공배수로 다시 두 수의 최소공배수를 구하고, 이를 끝까지 반복하여 나온 수가 최종 최소공배수가 되는 것이다.
결과적으로 내가 일반적으로 최소공배수를 구하는 방법이라고 생각했던 케이스1이 특이 케이스인 것이고, 실제로, 일반적으로 여러 수에 대한 최소공배수를 구하는 방법이 케이스2인 것이다.
function solution(arr) {
const n = Math.max(...arr);
for (let i = n; i >= 1; i--) {
const tmp = [];
for (let j = 0; j < arr.length; j++) {
if (arr[j] % i === 0) tmp.push(arr[j] / i);
else break;
}
if (tmp.length === arr.length) {
return tmp.reduce((a, c) => a * c, 1) * i;
}
}
}특이 케이스를 일반화한 코드 🥲 몰랐었다... 이게 특이 케이스인지...