# [완전탐색][Lv2] - 소수찾기 자바스크립트 js

# 프로그래머스 문제

https://programmers.co.kr/learn/courses/30/lessons/42839?language=javascript# (opens new window)

# 시도 1.

getNumbers 함수 : 들어온 문자로 조합 가능한 모든 수를 구한다.

재귀 함수로 해야겠다는 건 알겠는데 감이 안잡혀서 일단 for문으로 대충 써봤다.

for(let i=0; i<len; i++){
        numbers[i] 넣음
        for(let j=i; j<len; j++){
            numbers[i]+numbers[j] 넣음
            ... 문자열 길이만큼 반복
        }
    }

이걸 토대로 재귀함수를 만듦.

parents : string, 앞에서 붙인 문자열. 초기값은 빈값이다.
nowIdx : 앞에서 붙인 문자열의 idx(idx로 해야 중복 숫자가 들어왔을 때 처리 가능)
1. 0부터 문자열 끝까지 for문을 돌며 parents+numbers[i] 를 push 한다.
2. 만약 이미 거쳐간 문자열이라면 push 하지 않는다.
3. 문자열의 전체 길이와 parents(앞에서 붙인 문자열)의 길이가 다르다면 한번 더 탐색한다.

처음엔 for(let i=parentsLen; i<len; i++) 으로 했더니 1, 7 로 조합할 때 71 이 안나왔다.

그래서 i=0 으로 수정했더니 이번엔 선택했던 수를 또 선택하여 문제가 생겼다.

그래서 nowIdx 를 두고, 붙인 숫자의 idx를 담아 같은 수를 선택하지 않도록 했다.

중복제거, 0과1 빼는 걸 안해서 틀렸었다.

중복제거는 set으로 했는데 string인 상태로 했더니 001, 01 이런 친구들을 다르게 판단해서

string array→ int array→ Set → array 의 순서로 바꿔주었다.

function getNumbers(numbersList, numbers, parents='', nowIdx=[]){
    const len = numbers.length;
    const parentsLen = parents.length;
    
    for(let i=0; i<len; i++){
        var _nowIdx = nowIdx.slice();
        if(nowIdx.indexOf(i) === -1){
            numbersList.push(parents+numbers[i]);
            _nowIdx.push(i);
        }
        
        if(nowIdx.indexOf(i) === -1 && parentsLen+1 !== len){
            getNumbers(numbersList, numbers, parents+numbers[i], _nowIdx);
        }
    }
    
    return numbersList
}

function solution(numbers) {
    const len = numbers.length;
    let numbersList = [];
    let answer = 0;
    
    // 조합 되는 모든 수 구하고 숫자 배열로 바꾼 다음 중복 제거
    numbersList = [...new Set(getNumbers(numbersList, numbers).map(v=>+v))];
    
    // 2부터 그 수-1 까지 나눠지지 않으면 소수
    numbersList = numbersList.filter((e) => {
        for(let i=2; i<e; i++){
            if (e%i === 0) return false;
        }
        return true;
    })
    
    answer = numbersList.length;
    
    // 0, 1 제외
    if (numbersList.indexOf(0) !== -1) answer--;
    if (numbersList.indexOf(1) !== -1) answer--;
    
    return answer;
}

정확성  테스트
테스트 1 〉	통과 (0.23ms, 30.2MB)
테스트 2 〉	통과 (14.97ms, 33.9MB)
테스트 3 〉	통과 (0.18ms, 30MB)
테스트 4 〉	통과 (6.53ms, 33.7MB)
테스트 5 〉	통과 (11.44ms, 35MB)
테스트 6 〉	통과 (0.17ms, 30MB)
테스트 7 〉	통과 (0.20ms, 29.8MB)
테스트 8 〉	통과 (12.75ms, 34.7MB)
테스트 9 〉	통과 (0.20ms, 30.1MB)
테스트 10 〉	통과 (125.23ms, 33.8MB) <- 이거 시간을 줄이고 싶다
테스트 11 〉	통과 (6.68ms, 32.4MB)
테스트 12 〉	통과 (0.84ms, 29.9MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0

# 다른 사람의 답변/질문에서 효율성 찾기

테스트 10의 시간을 줄일 아이디어가 있을 까 싶어서 통과 한 다음 질문하기와 다른사람의 풀이를 봤다.

~~수학을 잘 몰라서요..~~ 소수인지 판단할땐 i까지 모두 나누지 않아도 된다고 한다. 제곱근 이하까지만 나누어봐도 판단이 가능하다.

// 2부터 그 수의 제곱근 까지 나눠지지 않으면 소수
numbersList = numbersList.filter((e) => {
    let sqrt = Math.sqrt(e);
		// 꼭 <= 이어야 한다. 제곱근'까지'임. = 빼면 테스트 케이스 몇개 통과 못함
    for(let i=2; i<=sqrt; i++){ 
        if (e%i === 0) return false;
    }
    return true;
})

채점을 시작합니다.
정확성  테스트
테스트 1 〉	통과 (0.27ms, 30.1MB)
테스트 2 〉	통과 (6.44ms, 33.8MB) <- before (14.97ms, 33.9MB)
테스트 3 〉	통과 (0.13ms, 30.3MB)
테스트 4 〉	통과 (4.83ms, 33.5MB)
테스트 5 〉	통과 (11.79ms, 35MB)
테스트 6 〉	통과 (0.21ms, 30.1MB)
테스트 7 〉	통과 (0.29ms, 30.1MB)
테스트 8 〉	통과 (12.57ms, 34.8MB)
테스트 9 〉	통과 (0.21ms, 30MB)
테스트 10 〉	통과 (5.66ms, 33.7MB) <- before (125.23ms, 33.8MB) 
테스트 11 〉	통과 (0.87ms, 30.1MB) <- before (6.68ms, 32.4MB)
테스트 12 〉	통과 (0.67ms, 29.9MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0

완전 많이 줄어들었다!!

← [힙][Lv3] 이중우선순위큐 - 자바스크립트 js [완전탐색][Lv2] - 카펫 자바스크립트 js →