[프로그래머스] 소수 찾기

그나마 소수 문제는 풀기 쉬워서 그나마 빨리 풀었습니다.

(이런 문제만 있었으면ㅋㅋㅋ)

---

접근방법

소수문제는 이전에 몇 개 소개해준 적이 있어요.

이번에도 평소에 소수문제 푸는 방식을 적용하여 풀었습니다.

 

예를 들어 '17'이면

1. [1, 7, 17, 71]을 만들고
2. [1, 7, 17, 71]에서 소수가 몇 개인지 구했습니다.

-> 7, 17, 71이 소수임으로 답은 3

 

 

좀더 자세한 방법을 설명하자면

'17'로 만들 수 있는 가장 큰 수는 71입니다.

그럼 2 ~ 71 숫자들 중에서 1,7이 있는 숫자를 찾고 그 값이 소수인지를 확인하면 됩니다.

 

여기서 주의해야 될 점은 11은 '17'로 만들 수 없는 수입니다.

왜냐하면 '17'에는 1이 1개만 있기 때문에 1이 두개가 있는 11은 할 수 없습니다.

이 부분까지 신경쓰면서 풀면 됩니다.

 

 

소수 구하는 방법은 전에도 설명했지만

소수를 구할 때는 2가지 중 어떤 상황인지 판단하고 그 상황에 따라 코드를 적용하면 됩니다.

1. 특정 수가 소수인지 아닌지 판별해야 되는 경우
2. 특정 범위가 주어지고 그 범위 내의 모든 소수를 찾아야 하는 경우

저는 이번에 특정수가 소수인지를 확인할 거기 때문에 1번 방법을 사용했습니다.

1번 방법에 대한 설명은 아래 링크에 잘되어 있습니다.👇

https://development-piece.tistory.com/105

[프로그래머스] k진수에서 소수 개수 구하기

---

해결방안

function solution(numbers) {
    let numbersArr = numbers.split('');
    let max = numbersArr.sort((a,b)=> b-a).join('')/1    

    let answer = 0;
    for(let i=2; i<=max; i++){
        let numArr = [...numbersArr];
        let trueNum = `${i}`.split('');
        let count = 0;
        for(let j=0; j<trueNum.length; j++){
            let idx = numArr.indexOf(trueNum[j]);     
            if(idx !== -1){
                count++;
                numArr.splice(idx, 1);
            }
        }
        if(count === trueNum.length){
            let isPrime = true;
            for(let k=2; k<=Math.sqrt(i); k++) {
                if(i % k == 0) isPrime = false;
            }
            if(isPrime) answer++;
        }
    }
    return answer;
}

 

해결방안 순서

1. 숫자문자열 numbers를 배열로 만들고, numbers로 만들 수 있는 가장 큰 수를 구한다.
2. for문으로 2~max 반복해준다.
3. 현재숫자(i)가 numbersArr에 있는지 확인한다.
4. 현재 숫자(i)가 numbersArr에 해당한 수이면 소수인지 확인한다.

 

1단계. 숫자문자열 numbers를 배열로 만들고, numbers로 만들 수 있는 가장 큰 수를 구한다.

let numbersArr = numbers.split('');
let max = numbersArr.sort((a,b)=> b-a).join('')/1

numbersArr

numbersArr은 3단계에서 사용하기 위해 미리 만들어주었습니다.

 

max

numbers로 만들 수 있는 가장 큰수(max)를 구하기 위해 numbers을 배열로 만들고 내림차순으로 정렬하고 다시 합쳐주었습니다.

max는 2단계~4단계에서 for문에 사용할거기때문에 숫자여야 됩니다. 그래서 "문자열과 숫자열의 사칙연산"을 사용해주었습니다.

 

2단계. for문으로 2~max 반복해준다.

for(let i=2; i<=max; i++){
        let numArr = [...numbersArr];
        let trueNum = `${i}`.split('');
        let count = 0;
}

for문을 2부터 시작한 이유는 1은 소수가 아니기 때문에 2부터 시작했습니다.

 

numArr

numArr은 3단계에서 사용해줄 numbersArr을 복사해주었습니다.

복사해준 이유는 3단계에서 사용한 숫자를 제거할건데 다 사용한 뒤에 다시 원래대로 돌려놔야 돼서 복사해주었습니다.

자세한 내용은 3단계에서

 

trueNum

trueNum은 3단계에서 사용하기 위해 미리 배열로 만들었습니다.

만약 i=17이면 ['1', '7']이 됩니다.

 

count

count는 3단계에서 현재숫자(i)가 numArr에 있는지 확인한다. 사용하기 위해 만들었습니다.

자세한 내용은 3단계에서

 

3단계. 현재숫자(i)가 numArr에 있는지 확인한다.

for(let j=0; j<trueNum.length; j++){
    let idx = numArr.indexOf(trueNum[j]);     
    if(idx !== -1){
        count++;
        numArr.splice(idx, 1);
    }
}

for문으로 trueNum의 원소를 차례대로 꺼내도록 했습니다.

 

idx

idx는 trueNum의 원소가 numArr에 있는지 확인해줍니다.

 

i=17일 때 i가 numArr에 해당되는 숫자인지 확인하자면

• trueNum=['1', '7']
• j는 0, 1 총 두 번 반복합니다.
• j=0이면 trueNum[j]='1'이고, idx=0이 됩니다.
  idx는 -1이 아니므로 count++이 돼서 count=1이 되고, numArr에서 '1'를 제거해줍니다.
• j=1이면 trueNum[j]='7'이고, idx=1이 됩니다.
  idx는 -1이 아니므로 count++이 돼서 count=2이 되고, numArr에서 '7'를 제거해줍니다.
• i=17이면 count=2가 됩니다.
  count값이 trueNum의 길이가 같으면 numArr에 해당되는 숫자입니다.

trueNum[j]가 numArr에 있을 때 제거한 이유는

11 같은 숫자가 있기 때문입니다.

11은 '1'이 있지만 numArr에서는 '1'이 두 개가 아닌 1개만 있으므로 11은 아닙니다.

여기서 해당되는 숫자를 numArr에서 미리 제거를 안 해주면 11이 numArr에 해당되는 숫자가 됩니다.

 

4단계. 현재 숫자(i)가numbersArr에 해당한 수이면 소수인지 확인한다.

if(count === trueNum.length){
    let isPrime = true;
    for(let k=2; k<=Math.sqrt(i); k++) {
        if(i % k == 0) isPrime = false;
    }
    if(isPrime) answer++;
}

 

특정 숫자가 소수인지 확인하는 방법은 아래와 같습니다.👇

let isPrime = true;
for(let j=2; j<=Math.sqrt(특정숫자); j++) {
    if(특정숫자 % j == 0) isPrime = false;
}

 

3단계에서 numArr에 해당되는 숫자를 찾았으면 그 숫자를 가지고 소수가 아닌지 구했습니다.

isPrime가 ture이면 answer++해주면 됩니다.

그러면 numArr에 해당되는 숫자이면서 소수인 값이 몇 개인지 찾을 수 있습니다.

---

여기까지 프로그래머스 소수 찾기 구하기 해결방안에 대해 설명해보았습니다.