[JavaScript] 소수 만들기 Lv1

문제명

문제 프로그래머스 FAQ 내용을 보니 카카오나 기업의 문제들은 저작권이 있으니 풀이를
github나 개인블로그에 올리지 말라고 되어 있어서 링크로 대체합니다.

출처: Programmers
소수 만들기

문제의 이해

소수란? 1과 자기 자신을 제외한 어떠한 약수도 가지지 않는 1보다 큰 자연수 내가 알기로는 아직도 소수라는 것을 구하고 있는 걸로 알고 있다. 물론 슈퍼컴퓨터같은 것을 통해서 말이다. 그러므로 소수는 정의할 수는 있어도 아직 우리는 모든 소수를 알 수는 없다. 그러므로 이 문제를 조금 더 깔끔하게 풀기 위해서는 주어진 범위 내에서의 소수만 판별하는 것이 좋아보인다.

내가 생각한 풀이 방법

1. 주어진 조건은 최대로 비교해야할 숫자는 50개, 각 숫자는 1000이하의 자연수이다. 이때 최대로 나올 수 있는 소수의 범위는 약 50000 이라고 가정하고 50000이하의 소수를 구해서 저장한다.
2. 숫자를 3개씩 더했을 때 그 숫자를 미리 구해놓은 소수묶음과 비교해서 존재한다면 그것은 소수이고 존재하지 않으면 소수가 아니다.
3. 숫자를 3개씩 더했을 때 더한 3개끼리 중복되지 않아야한다.
4. 중복되지 않는 숫자 3개를 최소한으로 구하는 방법(주어진 배열 [1,2,7,6,4]) 4-1. 맨 처음 값 1,2,7을 구한다. 이때 화살표 3개가 각각 1,2,7을 가리키고 있다고 생각하자. 4-2. 다음 값으로는 7을 가리키는 화살표 하나를 오른쪽으로 이동한다. 1,2,6이 나온다. 그리고 다시 6의 화살표를 한칸이동 1,2,4 4-3. 이제 3번째 값을 가리키는 화살표는 더 이동할 곳이 없다. 2번째 값을 가리키는 화살표를 1칸 오른쪽으로 이동하고 3번째 화살표는 2번째 화살표의 오른쪽 1칸 옆으로 다시 오면 1,7,6이다. 4-4. 다시 3번째 값 화살표 이동 1,7,4이다. 또 3번째 화살표가 갈 곳이 없으니 2번째 화살표를 이동 1,6,4이다. 3번째 화살표와 2번째 화살표가 더 이동할 곳이 없으니 1번째 화살표를 이동시키고 2번,3번 화살표를 옆으로 옮긴다. 2,7,6이다. 4-5. 3번째 화살표 이동 2,7,4이다. 다시 2번째 화살표 이동 2,6,4이다. 마지막으로 2번,3번 화살표가 이동할 곳이 없으니 1번 화살표를 이동시키면 7,6,4이다. 더 이상 이동할 수 있는 곳이 없으니 이대로 종료. 4-6. 중복되지 않는 3개를 더하는 방법의 갯수는 127,126,124,176,174,164,276,274,264,764 총 10가지이다.
5. 이렇게 구해진 10가지의 숫자합을 가지고 미리 구해놓은 소수묶음과 비교하여 구할 수 있는 소수가 몇개인지 판별해서 저장 출력한다.

풀이

첫 번째 풀이

생각한 풀이방법과 거의 동일하게 풀어봤다. 자잘한 오류들을 제외하고는 크게 문제는 없었다. 다만 내가 생각하는 2가지의 문제.

1. 속도가 너무 느리다.
2. 코드가 지저분하다. 2번 코드가 지저분한것은 솔직히 당장 어떻게 바꿀 수 있는 부분이 아닌 것 같고 계속해서 바꿔나가야 한다고 생각한다. 다만 1번 속도가 너무 느린 건 현재 당장 바꿔야 된다고 생각했다. 특히 풀고나서 다른 사람의 풀이를 봤는데 나보다 몇배는 빨랐다. 굳이 베끼고 싶지는 않아서 코드를 자세히 보지는 않았지만, 아마도 내 코드상에서 50000이라는 수치가 잘못됐다는 생각이 들었다.

function solution(nums) {
    var answer = 0;
    var primeNumberArr = [50000];

    //소수를 담을 50000개의 배열을 1로 초기화
    for(let i = 0; i < 50000; i++){
        primeNumberArr[i] = 1;
    }

    //50000까지 1로 채운 배열에서 값 1은 소수고 0은 소수가 아니게 만들기 위한 반복문
    //에라토스테네스의 체를 이용
    for(let i = 2; i < 50000; i++){
        var j = 2;
        while(true){
            if(i * j > 50000){
                break;
            }
            primeNumberArr[(i * j) - 1] = 0;
            j++;
        }
    }

    //주어진 숫자배열에서 중복없이 3개의 숫자를 더해서 소수가 맞는지 판별하는 반복문
    for(let i = 0; i < (nums.length - 2); i++){         //첫 번째 자리
        for(let j = 1 + i; j < (nums.length - 1); j++){ //두 번째 자리
            for(let k = 1 + j; k < nums.length; k++){   //세 번째 자리

                // console.log(nums[i],nums[j],nums[k]);
                // console.log(primeNumberArr[nums[i]+nums[j]+nums[k] - 1]);
                answer += primeNumberArr[nums[i]+nums[j]+nums[k] - 1];
            }
        }
    }
    return answer;
}

두 번째 풀이

속도가 너무 느린걸 파악하고(물론 처음부터 예상은 했지만) 고쳐보기로 했다. 일단 50000이라는 숫자가 나온 경우를 살펴봤다. 주어진 조건 최대 50개의 숫자이고 하나의 숫자는 1000보다는 작은 수 라서 50000이라고 잡았는데 생각해보니 최대 50개이지만 그 중 3개의 수를 더하는 것이고 3개의 소수가 각각 998 999 1000 이라고 해도(물론 소수는 아니지만) 3000보다는 작은 수이다. 그래서 소수를 가지고 있는 배열의 수를 50000 -> 3000으로 확 줄였다. 또 에라토스테네스의 체를 이용했다고 생각했는데 나는 에’체의 반만 알고 있었다. 1을 제외한 2이상의 소수에서 소수 자신을 제외한 배수를 모두 빼면 된다는 것은 알았는데 그것을 구하는 수까지 몇번 해야하는지는 모르고 있었다. 검색을 통해 알게되었는데 소수를 구하는 최대수의 제곱근까지만 하면 된다는 것이었다. 그러므로 50000 이 구해야할 최대 소수라면 223까지만 하면 됐었고 3000이 최대라면 54까지만 하면 된다. 이렇게 하니까 내 느린 코드의 속도를 다른 사람의 풀이보다 더 빠르게 할 수 있었다.

다만 여기서 하나 더 고쳐야 한다면 주어진 조건을 기준으로 3000이라는 숫자를 지정했는데 그것보다는 좀 더 유동적으로 코드를 짜는 것이 좋다고 생각한다.

const MAXPRIME = 3000;  //주어진 조건에 따른 최대 소수값
const MPSQUAREROOT = parseInt(Math.sqrt(MAXPRIME));   //최대 소수의 제곱근

function solution(nums) { 
    var answer = 0;
    var primeNumberArr = [MAXPRIME];
    

    //소수를 담을 3000까지의 배열을 1로 초기화
    for(let i = 0; i < MAXPRIME; i++){ 
        primeNumberArr[i] = 1;
    }

    //3000까지 1로 채운 배열에서 값 1은 소수고 0은 소수가 아니게 만들기 위한 반복문
    for(let i = 2; i <= MPSQUAREROOT; i++){
        var j = 2;

        //현재 주어진 숫자가 이미 소수가 아니라고 판명됐으면 continue
        if(primeNumberArr[i - 1] == 0){ 
            continue;
        }
        while(true){
            if(i * j > MAXPRIME){
                break;
            }
            primeNumberArr[(i * j) - 1] = 0;
            j++;
        } 
    }

    //주어진 숫자배열에서 중복없이 3개의 숫자를 더해서 소수가 맞는지 판별하는 반복문
    for(let i = 0; i < (nums.length - 2); i++){         //첫 번째 자리
        for(let j = 1 + i; j < (nums.length - 1); j++){ //두 번째 자리
            for(let k = 1 + j; k < nums.length; k++){   //세 번째 자리

                answer += primeNumberArr[nums[i]+nums[j]+nums[k] - 1];
            }
        }
    }
    
    return answer;
}

ps. 다음 문제가 소수 찾기 였는데 이 문제의 코드를 가져가서 풀어보니 하나의 문제가 발생했다. for(let i = 2; i < MPSQUAREROOT; i++){} 이 반복문에서 MPSQUAREROOT이 값보다 작다라는 조건인데 정확한 값을 얻기 위해서는 작거나 같다로 해야한다. 이유는 소수는 정수만있어서 parseInt로 소수점 부분을 버리고 정수 부분만 취했을 때 해당 정수 또한 소수일 수 있는데 조건을 작다로 하면 해당 소수는 검사를 하지 않기 때문이다. (현재는 수정함.)