이런 문제는 뭔가 창의력을 요하기엔 재능의 영역이고, 그냥 한번 외워버리면 평생 안까먹을 문제다.
이런 알고리즘 문제로 변별력을 만들 수 있을지는 모르겠다.
에라토스테네스의 체
function solution(nums) {
let answer = 0;
const length = nums.length;
for (let i = 0; i < length; i++) {
for (let j = i + 1; j < length; j++) {
for (let k = j + 1; k < length; k++) {
const sum = nums[i] + nums[j] + nums[k];
if (isPrime(sum)) answer += 1;
}
}
}
return answer;
}
function isPrime(num) {
for (let i = 2; i <= Math.sqrt(num); i++) {
if (num % i === 0) return false;
}
return num >= 2;
}다른 분의 코드를 가져왔다. 처음에는 해석하는 것도 쉽지 않았는데, 몇 번 적어보니 잊어버리지 않을 것 같다.
코드를 해석하면, for문 3개와 소수를 판별하는 함수가 나온다.
for문에는 i,j,k총 3개의 숫자를 만들기 위함이고,
숫자 4개의 배열[1,2,3,4]을 예로 들어보자 (숫자가 아닌 배열의 길이에만 집중)
모든 for문에는 length만큼이니 4개일 것이고, 제일 처음 돌아가는 for문에 i,j k = 0,1,2다. 그럼 nums[0]+nums[1]+nums[2]가 되고, 처음 for문이 끝나는 시점은 k부터다. k의 범위는 2,3이니까
0,1,2와 0,1,3을 가지게 된다.
그 다음 for문은 j다 제일 처음 1로 시작했기에 2부터 돌린다.
그러면 i,j,k= 0,2,~가 되는데, k는 j가 커지는 만큼 똑같이 커진다(k=j+1, 즉 k도 3부터 for를 돌린다)
그러면 j가 2일때 k는 3부터 시작. 0,2,3만을 가진다
마지막 i이다.
위쪽의 for문이 다 돌았고,
i=1일때,j는 2부터 ,k는 3부터 시작이다.
그럼 1,~이 되는데 1,2,3만을 가진다
총 4개의 배열이 나왔다. 실제로 이 배열은 4c3의 갯수와 똑같고,
5개를 돌려도 5c3인 543/321 = 10개가 나온다.
다음 if문에 들어가는 함수는 소수를 판별하는 함수이다.
소수는 2이상의 숫자이며, 소수의 제곱근만큼 for문을 돌린 후 그 제곱근보다 작은 정수들을 나눴을 때, 나머지가 0이되면 소수가 아니고, 0이 아니면서 2보다 크면 소수가 된다. 예를 들면 17의 제곱근은 4와 5사이에 있다. 그러면 for문은 i=2,3,4로 세번돌며 17%2,3,4를 진행한다. 17은 이 3번에 전부 나머지가 남으며 2보다 크다 =소수
돌아와서 아까 생성한 [1,2,3,4]에서 나온 3개의 숫자들을 살펴보면
012,013,023,123(배열위치)는 1+2+3,1+2+4,1+3+4,2+3+4
=> 6,7,8,9가 나오고, 6(제곱근은 2와 3사이)%2,3
7(2,3사이)%2,3, 8(2와 3사이)%2,3, 9(3)%2,3 가 되어,
6,8,9는 2와 3에 의해 나머지가 0인 상태가 되어 false,
7은 2보다 크면서 나머지가 2,3에의해 0이되는 경우가 없으므로 true
이렇게 answer에 1씩 추가해서 값을 반환하게 된다.
쓰고나니 장황하다.
결론
주어진 시간안에 이 문제를 푸는데 체로 거르고 있을 머리도 안될뿐더러, 만든다해도 아마 면접까지 끝난 뒤가 될 것이라고 생각한다. 별로 좋아하지는 않지만 이런문제는 한두번 풀면 외워질 것 같다.
