🗒️ 문제
양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.
- 0P0처럼 소수 양쪽에 0이 있는 경우
- P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
- 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
- P처럼 소수 양쪽에 아무것도 없는 경우
- 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
- 예를 들어, 101은 P가 될 수 없습니다.
예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.
정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.
⚠ 제한사항
- 1 ≤ n ≤ 1,000,000
- 3 ≤ k ≤ 10
📝 문제 해설
정답률이 59%(23.06.15 기준) 문제여서 겁을 먹고 들어갔었는데 생각보다 문제 로직을 짜는데 큰 어려움이 없었다. 아마 n을 k진수로 나타내는 과정에서 큰 어려움이 있어 보였는데 JavaScript에서는 toString(N) 메서드를 이용하면 원하는 진수의 수로 변환이 가능하기 때문에 큰 어려움은 없었다.
k진수로 변환한 후에 for문을 통해 문자를 하나하나 순회하면서 0이 나오기 전까지는 수를 문자열에 누적하여 계산하고 0이 나오는 순간에 새로운 배열에 숫자를 push하였다. 그렇게 원하는 값을 1차적으로 걸러내고 2차과정에서는 우리가 원하는 소수를 찾는 과정이었다.
이전 프로그래머스 문제에서 겪은 바 이중 for문을 사용할 때 원소 하나를 1부터 원소값까지 순회하면서 소수를 찾는 것은 시간초과가 뜰 확률이 1000%였다. 그래서 1부터 원하는 수의 제곱근까지 순회하면서 나누어 떨어지는 수가 1인 겨우에만 카운트를 하나씩 증가해줬다. 이 제곱근을 사용하는 것이 시간초과를 해결하는 방법 중 하나이다. 그리고 카운트가 1인 경우에만 총 카운트를 하나씩 증가해주고 그 최종 카운트 값을 리턴하면 문제는 해결된다.
💡 필요 문법
num.toString(N)
숫자가 담긴 num을 N진수로 변환한 문자열을 리턴한다.
push()
배열에 가장 끝 자리에 원하는 값을 삽입한다. 리턴값은 배열의 사이즈이다.
Math.sqrt(N)
int형 N의 제곱근을 반환하는 수식이다.
Math.floor(N)
int형 N의 소수점을 제외한 정수형만 반환하는 수식이다.
💻 코드
function solution(n, k) {
let str = n.toString(k); // 문자열 n을 k 진수로 변환
let num = ""; // 문자열을 순회하면서 0이 아닌 문자열 담기
let arr = []; // 문자열 num을 담을 배열
let result = 0; // 최종 결과값 출력을 위한 초기값 설정
// 문자열에서 0을 만나기 전까지의 수를 합쳐서 0을 만나게 되면 배열에 push
for(let i=0; i<str.length; i++){
if(str[i] !== "0") num += str[i];
else if(str[i] === "0"){
if(num !== "") arr.push(num);
else continue;
num = "";
}
}
arr.push(num);
let cnt;
// 배열을 순회하면서 소수(Prime Number 찾기)
for(let i=0; i<arr.length; i++){
cnt = 0; // 순회를 한번 할 때마다 카운트 초기화
if(arr[i] === "1") continue; // 1은 소수가 아니기 때문에 skip
for(let j=1; j<=Math.floor(Math.sqrt(Number(arr[i]))); j++){
if(arr[i]%j === 0) cnt++; // j로 나누어 떨어지면 카운트 증가
}
if(cnt === 1) result++;
}
return result; // 최종 카운트 값 리턴
}