[JS] 소수찾기 - 부제: 이거 외되.......? (진짜 모름)

여러분들 정말 자바스크립트의 기묘한 걸 찾아냈습니다.

혹시 왜이런지 아시는 분 있으면 알려주시면 너무 좋을 것 같아요.

오늘 풀어볼 문제는 프로그래머스 Level 2의 소수 찾기 입니다.

 

일단 같이 한번 볼까요?

---

문제 요약

numbers	return
"17"	3
"011"	2

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

 

문제 해석

자 일단 소수를 구하는 알고리즘은 너무너무 유명한 에라스토테네스의 체를 써볼까 합니다.

문자열의 최대 크기가 7자리이고 최대 들어갈 수 있는 수가 9이기 때문에 numbers의 최대는 "9,999,999"입니다.

그러니 에라토스테네스의 체를 최적화한 제곱근 기준으로 루프를 돌리면 배열 크기를 천 만의 제곱근인 3162안으로 끊어낼 수 있습니다.

 

또 중요한 건 이제 숫자카드의 조합을 모조리 찾아내는게 중요한데요.

여기서 이제 기묘한 모험 시작입니다.

일단 코드 먼저 보여드릴게요.

 

정답 코드?

function allItems(numbers) {
    if (numbers.length === 1) return numbers;
    const result = new Set();
    numbers.forEach((fixed, i, arr) => {
        const rest = arr.filter((_, ai) => i !== ai);
        const combi = allItems(rest);
        result.add(fixed);
        const item = combi.forEach(v => result.add(fixed + v));
    });
    return [...result];
}

function solution(numbers) {
    const targets = allItems(numbers.split(""));
    const max = Math.max(...targets);
    const primes = Array.from({length: max + 1}, () => true);
    primes[0] = false;
    primes[1] = false;
    for (let i = 2; i < Math.sqrt(max); i++) {
        if (primes[i]) {
            for (let j = 2; j < max; j++) {
                if (i * j > max) break;
                primes[i * j] = false;
            }
        }
    }
    return targets.reduce((acc, val) => primes[val] ? acc + 1 : acc, 0);
}

 

팁 1. 순열 함수를 변형시킨 allItmes()에 대하여..

음.. 중복제거를 위해 Set()을 사용했습니다.

또, 원래 제가 쓰던 순열함수는 level을 인자로 넣어주면서 계속 재귀를 돌려줬었는데 모든 요소를 그냥 다 넣으면 되니까 안넣어도 됩니다.

일단 이렇게 하면 결과가 어떻게 나오냐면..

입력값	출력
"17"	['1', '17', '7', '71']
"011"	[ '0',  '01',  '011', '1',  '10',  '101', '11', '110' ]
"7492"	[ '7',    '74',   '749',  '7492', '742',  '7429', '79',   '794',  '7942', '792',  '7924', '72', '724',  '7249', '729',  '7294', '4',    '47', '479',  '4792', '472',  '4729', '49',   '497', '4972', '492',  '4927', '42',   '427',  '4279', '429',  '4297', '9',    '97',   '974',  '9742', '972',  '9724', '94',   '947',  '9472', '942', '9427', '92',   '927',  '9274', '924',  '9247', '2',    '27',   '274',  '2749', '279',  '2794', '24',   '247',  '2479', '249',  '2497', '29', '297',  '2974', '294',  '2947' ]

일단 모든 경우를 다 string 형태로 내보내줍니다.

왜 Number를 allItems에 안넣어줬냐면 예시 2번처럼 0이 있는 경우는 재귀를 돌다가 01이 1이 되면서 101이라는 케이스를 잡아내지 못하더라구요. 그냥 11로 나와요. 하위분기에서 01이 1이되니까

 

근데 웃긴게 이 값이 아래에 설명할 소수인지 아닌지 정의한 배열의 index로 사용하는데 그냥 string으로 넣어도 인식을 한다는게 진짜 이해가 안되버린다는 거에요.

일단 아래도 보고 다시 이야기해요 우리

 

팁 2. 에라토스테네스의 체(소수 구하기)

const max = Math.max(...targets); //일단 여기부터 이해 안됨.. 이거 string인데 왜 이거 되는거죠..?
const primes = Array.from({length: max + 1}, () => true); // 여기도 2222, 일단 각 값을 index로 쓸거라서 max + 1해줬습니다.
primes[0] = false;
primes[1] = false; // 0, 1은 일단 소수아니니까 false
for (let i = 2; i < Math.sqrt(max); i++) { // 합성수는 무조건 그 수의 제곱근 이하에서 약수가 있습니다. ex 1, 3, 9
    if (primes[i]) {
        for (let j = 2; j < max; j++) {
            if (i * j > max) break;
            primes[i * j] = false;
        }
    }
}

일단 가장 이해안되는건 왜.. 도대체 javascript는 이 string을 숫자로 인식하는건가? 입니다.

알아서 그냥 치환되는건지... 잘 모르겠어요.

 

아래 reduce문에서도 그냥 prime의 index에 접근할 때 string 형식으로 접근했을 텐데.. (정의할 땐 위에 보시는 것 처럼 숫자로 넣어줬습니다.) 그냥 숫자로 인식해줍니다.

javascript의 배열은 object 객체라 index에 뭘 넣어도 인식가능하다고는 알고 있었는데 '01'과 1은 달라야하지 않나요...?

 

일단 좀 더 알아봐야할 것 같습니다.

아무튼 이렇게 최댓값까지 소수인지 아닌지 판별해주는 primes를 잘 설정해줍니다.

그 뒤로는 적절히 targets를 순회하면서 소수라면 카운터를 1올려주면 정답이 나오네요.

 

흠... 진짜 자바스크립트는 신기하네요.

js 객체에 대해서 좀 더 공부해야할 것 같습니다.

더 알아내는 대로 포스트에 추가해서 공유드릴게요.

 

그럼 이만!