[코딩테스트] 프로그래머스 - 소수 찾기 (lv2) in JavaScript

주어진 숫자들이 문자열로 입력될 때, 그 숫자들로 만들 수 있는 모든 수 들 중에 소수의 수를 리턴하는 문제이다.

 

ex. "23" ->  3 (2, 3, 23)

 

초보 of 초보여서 시간이 꽤 걸렸다...:')

그래도 하는 동안 재밌었고 답을 보지 않고 구현먼저 했다는 것에 의의를!!! ^.^

 

목차(?)
A - 입력된 문자열을 숫자 하나 하나로 나누기
B - 입력된 숫자가 소수인 지 체크
C - 인덱스 i와 j인 data list의 원소를 교환
D - nPr의 순열 조합 리턴
E - 모두 하나로 묶는 solution 함수

 

JavaScript 코드 구현 - 나의 전체 코드

// A - 입력된 문자열을 숫자 각각으로 separate 후 저장
function numbersToArray(numbers){
    const result = [];
    const lenNums = numbers.length;
    for (let i=0; i<lenNums; i++){
        result.push( parseInt(numbers[i]));
    }
    return result;
}

// B - 입력된 숫자가 소수인 지 체크
function isPrimeNum(checkNum){
	if (checkNum == 2) return true;
    if (checkNum < 2 || checkNum %2 == 0) return false;
    
    let sqrtNum = Math.sqrt(checkNum);
    for (let k=3; k<=sqrtNum; k+=2){
        if (checkNum % k == 0) return false;
    }
    return true;
}

// C - 인덱스 i와 j에 있는 data의 원소를 교환
function swap(data, i, j){
    if (i != j){
        let tmp = data[i]
        data[i] = data[j]
        data[j] = tmp
    }
}

// D - nPr의 순열 조합을 리턴
// data는 조합의 베이스가 되는 숫자들 (ex. [2, 3])
// resultArray는 모든 순열 조합이 원소로 추가된 리스트 (ex. [2, 3, 23, 32])
function Permutation(resultArray, data, depth, n, r){
    if (depth == r){
        let num = 0
        for (let i=0; i<r; i++){
            num = num * 10 + data[i]
        }
        if (!resultArray.includes(num) ) {
            resultArray.push(num)
        }
    }
    for(let i = depth; i<n; i++){
        swap(data, i, depth)
        Permutation(resultArray,  data, depth+1, n, r)
        swap(data, i, depth)
    }
    return resultArray
}

// E - 모든 걸 하나로 묶는 함수
function solution(numbers){
    const possibleNums = [] //모든 순열 조합이 추가될 리스트
    const numbersArray = numbersToArray(numbers) //문자열이 숫자 하나 하나로 나눠짐
    const lenNums = numbersArray.length //for loop에서 len을 반복적으로 구하지 않기 위해 미리 선언
    const answer = [] //순열 조합 중 소수인 것들만 추가될 결과 리스트

    // nPr에서 1 <= r <= n 일 때의 경우를 모두 구하므로 반복문으로 작성
    for (let i=0; i<lenNums;i++){
        Permutation(possibleNums, numbersArray, 0, lenNums,i+1)
    }
    
    const indices = possibleNums.length
	
    //answer 리스트에 들어있는 원소들이 각각 소수인 지 확인 후 맞다면 answer에 추가
    for (let i=0; i<indices ;i++){
        if(isPrimeNum(possibleNums[i])){
            answer.push(possibleNums[i])
        }
    }
    return  answer.length
}

 

A - 입력된 문자열을 숫자 하나 하나로 나누기

- 다른 분들의 풀이를 보니, 이렇게 쉬운 방법이 있더랬다...

const numbersArray = numbers.split('') //ex. numbers = '12'일 시, numbersArray는 ['1', '2']

- separator에 따라 다양하게 split할 수 있다

: developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/String/split

B - 입력된 숫자가 소수인 지 체크

function isPrimeNum(checkNum){
    if (checkNum == 2) return true
    if (checkNum %2 == 0 || checkNum < 2) return false
    
    let sqrtNum = Math.sqrt(checkNum)
    for (let k=3; k<=sqrtNum; k+=2){
        if (checkNum % k == 0) return false
    }
    return true
}

- 이 부분은 나도 검색을 하면서 배웠던 부분!

- 요지는, 소수 판별을 더 빨리 하기 위해: n이 소수인 지 판별할 때1. n < 2이면 제외2. n % 2 === 0 이면 제외3. n > 3일 때, (n % k === 0)에서 (k <= n)인 모든 k를 체크해보는 것보다, (k <= sqrt(n))을 체크하면 더 빠르다는 점.sqrt(n) = k라면 n = k^2이고,어차피 소수는 (소수, 소수와 곱해서 n이 나오는 수) 의 pair로 구해지기에여기까지만 구해도 충분하다.

 

ex. 6이 소수인 지 아닌 지 판별하고자 할 때,    1, 2, 3, 4, 5, 6으로 나눠지는 지 모두 확인할 필요가 없고,    1, 2, 3 (n/2) 까지만 확인해도 된다.    혹은 sqrt(6) = 2.45이기에,    1, 2까지만 확인해도 된다.    6은 이 때 1과 자기 자신을 제외한 수로 나눠지기에 (6 % 2 ===0)    소수가 아니다.

 

C - 인덱스 i와 j인 data list의 원소를 교환

D - nPr의 순열 조합 리턴

- 이 또한 검색을 통해 Heap's Algorithm이라는 순열 조합 알고리즘을 배우고 사용했다.

- 이 분의 블로그 글이 특히나 도움이 많이 되었다

: gorakgarak.tistory.com/522

순열(Permutation) 알고리즘

 

- 다른 분들의 코드를 보니, 다르게 조합이 구현된 것들이 많아 신기했다.

 

다른 순열 조합 구현 방법 예시:

let nums = new Set();

function permutation(a, s) {
	if (s.length > 0) { //A
        if (nums.has(Number(s))=== false) {
            nums.add(Number(s));
        }
    }
    if (a.length > 0) { //B
        for (let i = 0; i< a.length; i++) {
            let t = a.slice(0)
            t.splice(i,1);
            permutation(t,s + a[i]);
        }
    }
}



permutation(['1','2','3'],'')
//1, 12, 123, 13, 132, 2, 21, 213, 23, 231, 3, 31, 312, 32, 321

- Set (중복된 원소를 허용하지 않는 리스트)을 정의하여 유일한 원소들만 갖도록 함

  : 이 경우 코드 구현이 잘 돼있어 그냥 array여도 중복된 원소가 들어가지는 않을 것

 

- 이해를 위해 permutation(['1','2','3'], '')의 경우를 보자

 

  : 맨 처음에는 s = ''이므로 B부터 시작 // when a = ['1','2','3'] and i = 0

  : t에 a 리스트 전체를 복사 (slice(0)) // t = ['1','2','3']

  : t 리스트에서, 인덱스가 i인 1개의 원소를 없앰 // t = ['2','3']

  : permutation (t, s+ a[i]) //  이 경우, permutation (['2','3'], '1')과 동일

 

  : permutation(['2','3'], '1') 실행 시 => 이 때, for loop을 빠져나오지 않은 상태에서 재귀 호출! -  E

  : s 가 공백이 아니므로 (A 부분)도 실행

  : nums 리스트에 s 가 이미 없다면 숫자로 변환 후 추가 // ex. 1

 

  : (B 부분도 실행) // ex. s또한 공백이 아니므로

  : 현재 a = ['2','3'], s = '1', i = 0

  : permutation (['3'], '12') 실행 => for loop을 빠져나오지 않은 상태에서 재귀 호출! - D

 

  : (A 부분 실행)

  : nums에 12 추가

 

  : (B 부분 실행), 현재 a = ['3'], s = '12', i = 0

  : permutation ([''],'123') 실행 => for loop을 빠져나오지 않은 상태에서 재귀 호출! - C

 

  : (A 부분 실행)

  : nums에 123 추가

 

  : a가 빈 리스트이므로 (B 부분) 실행 안 함!

  : 따라서 더 이상의 재귀 호출은 일어나지 않는다

 

  : 재귀 호출 되었던 C로 복귀... // permutation 실행 시 i = 0 < a.length = 1이었으므로 반복 안 함.

  : 재귀 호출 되었던 D로 복귀...

  : i++ 후 i = 1일 때 반복 //permutation(['2'],'13') 실행 ~> 13, 132 추가. 이후엔 i = 1 < a.length = 2이므로 반복 안 함.

 

  : 재귀 호출 되었던 E로 복귀...

  : i++ 후 i = 1일 때 반복 //permutation(['1','3'], '2') 실행 ~> 위의 과정을 반복!

  : 반복...

 

 

트리 구조까지 들어가지 않고도 쓸 수 있는 방법이다!

 

 

E - 모두 하나로 묶는 solution 함수

- 다른 함수들을 정의할 때 여러 기능을 묶음으로서 이렇게 길어지지 않아도 될 것이다.

 

 

 

 

여러모로 개선점들이 보이는 코드지만, 이렇게 검색하고 다른 분들의 풀이를 보면서 배워나갈 수 있다는 것이 참 좋다!!