▷ 문제 : AVAILABLE LESSONS 11 - CountNonDivisible (Medium)
CountNonDivisible coding task - Learn to Code - Codility
Calculate the number of elements of an array that are not divisors of each element.
app.codility.com
▷ 해결 날짜 : 2022.04.25
▷ 소요 시간 : 1시간
▷ 풀이 과정 :
LESSONS 11이 에라토스테네스의 체 라는데, 이 문제가 그거랑 무슨 상관인지 전혀 모르겠다.
일단 이 문제는 주어진 배열 [3, 1, 2, 3, 6] 에서 각 인덱스에 해당하는 값의 약수가 아닌 것들의 수를 구해주면 된다.
예를 들어 0번 인덱스의 3인 경우 1, 3을 제외한 나머지 2, 6이 있기때문에 2를 반환해줘야한다.
그래서 결과는 [2, 4, 3, 2, 0]이 된다.
단순하게 이중 for문을 돌리게되면 당연히 답은 구할 수 있으나.
시간 복잡도에서 완전히 해결할 수 없다.
그래서 좀 다른 방식으로 접근을 해야한다.
이중 for문을 돌리는 방법은 맞는데, 거기서 시간복잡도를 줄여서 O(N**2) 를 O(N * log(N))으로 변경해줘야한다.
약수의 특징을 이용해서 반복의 제한을 두는 방향을 잡고 진행해야한다.
우선 각 숫자가 몇번 나왔는지 담아둘 수 있는 배열을 만들어준다.
여기서 순서대로 담을것이기 때문에 매개변수 배열의 최대값 + 1 만큼의 배열만 만들어주도록 하자.
그리고 이제 각 값에 대해서 약수의 개수가 몇개인지 체크를 하고 배열의 길이에서 약수의 개수만큼을 빼주면 답을 구할 수 있다. (약수 구하기 알고리즘)
▷ 구현
function solution(A) {
const arr = Array(Math.max(...A) + 1).fill(0);
A.forEach(e => {
arr[e]++;
}) ;
return A.map(v => {
let count = 0;
for(let i = 1; i * i <= v; i++){
if(v % i === 0) {
count += arr[i];
if(v / i !== i) count += arr[v / i];
}
}
return A.length - count;
});
}
▷ 복기 :
처음에는 약수 구할때 제곱근(Math.sqrt)을 사용해서 반복 횟수를 줄여 구해봤더니 이상하게 시간 초과가 걸리더라.
i * i 로 하는게 좀 더 빠른 모양이다.
댓글