문제
양의 정수 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 함수를 완성해 주세요.
💝 예시
💝 풀이 설명
- Integer 클래스의 toString() 메서드를 이용하여 n을 k진수로 변환한다.
- 그리고 0을 기준으로 문자열을 나누어 배열에 대입한다.
public static int solution(int n, int k) {
String s = Integer.toString(n, k);
String[] target = s.split("0");
}
- 소수를 판별할 함수를 만들어준다.
- 2보다 작으면 거짓, 2면 진실, 그리고 제곱근을 이용하여 소수를 판별한다.
private static boolean is_Prime(long num) {
if (num < 2) return false;
if (num == 2) return true;
for(int i = 2; i <= (int) Math.sqrt(num); i++) {
if(num % i == 0) {
return false;
}
}
return true;
}
- 개수를 리턴할 값을 cnt로 선언하고, 초기화한다.
- 반복문을 돌면서 해당 숫자들이 소수인지 아닌지를 확인한다.
- 0을 기준으로 잘랐기에 0이 겹치는 경우 빈 문자열이 배열로 들어가기 때문에, 빈 배열이면 continue를 이용하여 다음 반복문으로 넘어가도록 하였다.
- 만약 소수이면 ( 소수면 참을 리턴하도록 하였음) 개수를 ++시켜준다.
- 그리고 카운트한 결과를 리턴해준다.
public static int solution(int n, int k) {
...
int cnt = 0;
for (int i = 0; i < target.length; i++) {
if (target[i].equals("")) continue;
long num = Long.parseLong(target[i]);
if (is_Prime(num)) {
cnt++;
}
}
return cnt;
}
🦄 최종 풀이
public static int solution(int n, int k) {
String s = Integer.toString(n, k);
String[] target = s.split("0");
int cnt = 0;
for (int i = 0; i < target.length; i++) {
if (target[i].equals("")) continue;
long num = Long.parseLong(target[i]);
if (is_Prime(num)) {
cnt++;
}
}
return cnt;
}
private static boolean is_Prime(long num) {
if (num < 2) return false;
if (num == 2) return true;
for(int i = 2; i <= (int) Math.sqrt(num); i++) {
if(num % i == 0) {
return false;
}
}
return true;
}
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 17683. 방금 그곡 JAVA (0) | 2023.08.24 |
---|---|
[프로그래머스] 12973.짝지어 제거하기 JAVA (0) | 2023.05.19 |
[프로그래머스] 42895. N으로 표현 (0) | 2023.01.02 |
[프로그래머스] 42898. 등굣길 JAVA (0) | 2023.01.02 |
[프로그래머스] 43105. 정수 삼각형 JAVA (0) | 2022.12.30 |
댓글