프로그래머스 #JavaScript - 소수찾기

문제

https://programmers.co.kr/learn/courses/30/lessons/42839

풀이

1. me

function solution(numbers) {

    // 1. 가능한 모든 숫자 구하고 (=> 단순 순열이 아님. 자리수가 달라질 수 있기 때문)
    // 앞이 0인 경우 유의하기, 맨 뒤 0이면 무시 가능(소수 아니라서)
    // 단순 순열 아님 - 자리수가 달라지니까
    // 2. 소수인지 판별 - 맨 뒤 0이면 무시 가능(소수 아니라서)
    
    // 가능한 순열 중 가장 큰 수 -> 소수 구하고 -> 사용된 문자열
    var answer = 0;
    //가장 큰 수
    var numArr = numbers.split('');
    var sortedNum = numArr.sort((a,b) => b-a);
    var largest = numArr.join('');
    
    // 2~가장 큰 수 사이의 소수 모두 구하기
    var prime = [2];
    var count = 0; // 소수아님
    
    for( var i= 2; i<=largest; i++){
        var compare = Math.ceil(Math.sqrt(i));
        prime.push(i);
        for(var j=2; j<=compare; j++){
            // i 소수아님 -> prime에서 제거
            if(i % j === 0){
                count = count +1; //소수아닌 것의 개수 카운트
                prime.pop();
                break;    
            }       
        }
    }
    // i는 소수 -> 3. 주어진 숫자만 사용한 소수인지 확인

    for(var k=0; k<prime.length; k++){
        var newArr = numArr.concat();
        var toCompare = prime[k].toString().split('').sort((a,b) => b-a);
        for(var s=0; s<toCompare.length; s++){
            var index = newArr.indexOf(toCompare[s]); 
            if(index !== -1){   
              newArr.splice(index, 1);
            }else{
                 count = count + 1; // 소수 아닌 경우
                      break;
            }  
        }   
    }
    answer = largest - count;
    return answer;
}

2.other

https://velog.io/@fastpace04/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

더 생각해보기

참고사항

주어진 숫자를 모두 이용하는 순열

function solution(numbers) {
    var newArr = numbers.split('');
    
    function swap(newArr, idx1, idx2){
        var temp = newArr[idx1];
        newArr[idx1] = newArr[idx2];
        newArr[idx2] = temp;
    }
    
    function permute(newArr, begin, end){
        if(begin === end){
            console.log(newArr);
        } else {
            for (var i = begin; i<end+1; i++){
                swap(newArr, begin, i);
                permute(newArr, begin + 1, end);
                swap(newArr, begin, i);
            }
        }
    }
    
    function permuteArr(newArr){
        permute(newArr, 0, newArr.length-1);
    }
            
    console.log(permuteArr(newArr));
}

더 생각해보기

실수, 계속 놓치는 부분 - 문자열을 전부 사용해야 하는 것이 아니다!
포함관계인 두 문자열 비교?