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

이번 문제는 소수 구하는 방법만 아시면 쉽게 풀 수 있을 것 같아요.

 

---

접근방법

이문제는 문제 설명의 예시를 보시면 이해가 편합니다.

 

테스트 1 (n= 437674 k=3)

• 437674을 3진수로 바꾸면 211020101011
• 문제 설명에서 아래 조건에 맞는 소수(Prime number)가 몇 개인지를 파악하면 211, 2, 11
• 211, 2, 11이 10진수 기준으로 소수인 개수를 세면 됩니다.

 

사실 211020101011에서

211020101011

211, 2, 1, 1, 11 5가지 수가 가능하지만

"소수의 정의는 '1과 자기 자신으로밖에 나누어 떨어지지 않고 자기 자신의 곱셈의 역수가 없는 수'이다."임으로

1은 미리 제거하는게 좋다고 생각이 들었습니다.

그래서 1을 제거하면 211, 2, 11이 남습니다.

 

이제 이 211, 2, 11이 소수인지 아닌지 판별하면 됩니다.

소수를 구하는 방법은 프로그래머스 연습문제 레벨 1에서 여러 번 출제되었는데요.

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

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

 

1번은 "특정 수 % 2 ~ 특정 수의 제곱근"이 0인지 아닌지 확인하여 소수를 판단합니다.

전에 소수 만들기에 나와있긴 한데 이번에 또 설명할 거니까 보기 귀찮으시면 안 보셔도 됩니다.

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

[프로그래머스] 소수 만들기

 

2번은 에라토스테네스의 체를 이용해서 특정 범위 내의 소수를 찾습니다.

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

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

 

제 생각에 거의 공식 같은 거라 1번, 2번 둘 다 외우시는 게 좋을 것 같아요.

 

 

문제로 돌아와서 

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

이 두 가지 중 이번에는 1번에 경우에 해당이 됩니다.

211, 2, 11이 소수인지 아닌지 판단하기 때문입니다.

 

특정 수가 소수인지 아닌지 판별하는 방법은 해결방안에서 설명하겠지만,

간단하게 중요한 포인트를 얘기하자면

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

이게 소수 구하기 전부입니다.

---

해결방안

function solution(n, k) {    
    let arr = n.toString(k).split('0').filter(a => a/1 > 1);
    
    var answer = 0;
    for(let i of arr){
        let isPrime = true;
        
        for(let j=2; j<=Math.sqrt(i); j++){
            if(i % j == 0) isPrime = false;
        }
        if(isPrime) answer++;
    }
    return answer;
}

 

해결방안 순서

1. 숫자 n을 k진수로 바꾸고 조건에 맞게 추출한 뒤 1보다 작으면 제거하고 arr배열에 담아준다.
2. 1단계에서 만든 arr의 원소가 소수인지 아닌지 판별하고 소수가 맞으면 answer에 카운터 하기

 

1단계. 숫자 n을 k진수로 바꾸고 조건에 맞게 추출한 뒤 1보다 작으면 제거하고 arr배열에 담아준다.

let arr = n.toString(k).split('0').filter(a => a/1 > 1);

숫자n을 k진수로 바꿀 때는 toSting()을 사용해주었습니다.

 

k진수로 바뀌면 조건에 맞는 수만 따로 추출해줘야 되는데 저는 이때 split()를 사용해 주었습니다.

문제 설명에서 조건을 살펴보면

• 0P0처럼 소수 양쪽에 0이 있는 경우
• P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
• 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
• P처럼 소수 양쪽에 아무것도 없는 경우
• 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
  • 예를 들어, 101은 P가 될 수 없습니다.

위에 조건을 쉽게 해석하면 0이 기준이라는 말이고 0을 기준으로 값을 추출하면 됩니다.

그래서 split('0')을 넣어주었습니다.

테스트 1 (n= 437674 k=3)
n.toString(k).split('0') -> [ '211', '2', '1', '1', '11' ]

테스트 2 (n= 110011 k=10)
n.toString(k).split('0') -> [ '11', '', '11' ]

 

이제 여기서 ''이거나 1을 제거하면 됩니다.

제거하는 방법으로는 filter()를 사용했습니다.

a/1를 해준 이유는 콘솔 찍어보면 알겠지만 위에서 만든 값은 숫자가 아니라 문자열입니다.

그래서 "문자열과 숫자열의 사칙연산"을 사용하여 문자열을 숫자열로 바꾸어 주었습니다.

그럼 a/1 > 1이라 하면 1보다 큰 수만 추출되겠죠.

테스트 1 (n= 437674 k=3)
n.toString(k).split('0') -> [ '211', '2', '1', '1', '11' ]
n.toString(k).split('0').filter(a => a/1 > 1); -> [ '211', '2', '11' ]

테스트 2 (n= 110011 k=10)
n.toString(k).split('0') -> [ '11', '', '11' ]
n.toString(k).split('0').filter(a => a/1 > 1); -> [ '11', '11' ]

(''/1은 0입니다.)

 

 

2단계. 1단계에서 만든 arr의 원소가 소수인지 아닌지 판별하고 소수가 맞으면 answer에 카운터 하기

var answer = 0;
for(let i of arr){
    let isPrime = true;

    for(let j=2; j<=Math.sqrt(i); j++){
        if(i % j == 0) isPrime = false;
    }
    if(isPrime) answer++;
}
return answer;

 

*위에서 특정 숫자가 소수인지 아닌지 판별하는 방법*

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

 

 

j=2로 설정한 이유는 소수는 1과 자기 자신만 나누어지기 때문에 2로 설정하였고

여기서 중요한 점은 꼭 특정 숫자의 제곱근까지 해야 됩니다.

제곱근보다 큰 숫자부터는  2~특정 숫자의 제곱근 * a로 구성이 되어 있기 때문입니다.

 

이제 특정 숫자 % (2~특정숫자 제곱근)이 0이나오면 소수가 아니고

특정숫자 제곱근까지 했는데 0이 아니면 소수겠죠.

 

 

위의 코드를 적용하여, 1단계에서 만든 arr의 각 원소가 소수인지 아닌지 판별하고 몇 개인지 확인하면 됩니다.

for(let i of arr)

for of문을 사용하여 arr = [ '211', '2', '11' ]이라면 '211', '2', '11'순으로 반복하게 만들었습니다.

 

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

for of안에 소수 판별하는 코드를 넣어 소수를 판별하였고

(arr의 원소는 문자열인데 잘 작동하는 이유는 i%j또한 "문자열과 숫자열의 사칙연산"이기 때문입니다.)

 

if(isPrime) answer++;

해당 원소가 소수이면 answer++을 해주면 됩니다.

---

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