문제 설명
양의 정수 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
입출력 예
n k result
| 437674 | 3 | 3 |
| 110011 | 10 | 2 |
입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
110011을 10진수로 바꾸면 110011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 11, 11 2개입니다. 이와 같이, 중복되는 소수를 발견하더라도 모두 따로 세어야 합니다.
package LV2;
public class H92335 {
public int solution(int n, int k) {
// 변환된 k진수를 저장할 String 변수
String num = Integer.toString(n, k);
// k진수를 '0'을 기준으로 split
String[] numArr = num.split("0");
int count = 0; // 소수 개수를 저장할 변수
for (String str : numArr) {
// 공백은 continue
if (str.equals("")) continue;
// 10진법으로 변환
int decimalNum = Integer.parseInt(str);
// 소수 판별
if (isPrime(decimalNum)) {
count++;
}
}
return count;
}
// 소수 판별 메서드
public boolean isPrime(int n) {
if (n < 2) return false; // 2보다 작으면 소수 아님
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return false; // 나눠떨어지면 소수 아님
}
return true; // 그 외의 경우는 소수
}
}
런타임 에러….ㅠㅠㅠㅠ
실행 중에 예상치 못한 문제를 발견했을 때 발생한다. 일반적으로 런타임 에러의 원인은 잘못된 타입의 값이 함수에 전달되거나, 배열의 범위를 벗어나는 접근 등이 있다.
이 경우, **Integer.parseInt(str)**에서 발생할 수 있는 NumberFormatException 예외를 처리하지 않아서 그럴 수 있다. k진수로 변환한 수 중에서 10진법으로 표현할 수 없는 숫자가 있을 경우, **Integer.parseInt(str)**에서 NumberFormatException 예외가 발생할 수 있다.
package LV2;
public class H92335 {
// 소수 판별 함수
public boolean isPrime(long n) {
if(n == 1) return false; // 1은 소수가 아니므로 false 반환
long a = (long)Math.sqrt(n) + 1; // n의 제곱근 계산
for(int i=2;i<a;i++) { // 2부터 n의 제곱근까지 반복
if(n%i == 0) return false; // 나누어 떨어지는 수가 있으면 소수가 아니므로 false 반환
}
return true; // 나누어 떨어지는 수가 없으면 소수이므로 true 반환
}
// 주어진 숫자를 k진수로 바꾸고, 0을 기준으로 나누는 함수
public String[] makeBinList(int n, int k) {
StringBuilder kBin = new StringBuilder(); // k진수를 저장할 StringBuilder
while(n != 0) {
kBin.insert(0, n%k); // n을 k로 나눈 나머지를 문자열 앞에 추가
n /= k; // n을 k로 나눔
} // k진수 생성
String[] binList = kBin.toString().split("0"); // 생성된 k진수를 '0'을 기준으로 나눔
// 0을 기준으로 나눈 문자열 배열 반환
return binList;
}
// 솔루션 함수
public int solution(int n, int k) {
int answer = 0; // 소수의 개수를 저장할 변수
String[] a = makeBinList(n, k); // k진수로 변환된 문자열 배열을 가져옴
for(String b : a) { // 문자열 배열을 반복
if(b.equals("")) continue; // 문자열이 비어있으면 다음 반복으로 건너뜀
long c = Long.parseLong(b); // 문자열을 long으로 변환
if(isPrime(c)) answer++; // 변환된 숫자가 소수이면 answer 증가
}
// 소수의 개수 반환
return answer;
}
}
주어진 정수를 k진수로 변환하고, 이진수를 '0'을 기준으로 나눠 각 부분이 소수인지 확인하는 알고리즘을 구현한 것이다. 'isPrime' 함수는 주어진 수가 소수인지 판별하고, 'makeBinList' 함수는 주어진 수를 k진수로 변환한 후 '0'을 기준으로 나눠 문자열 배열로 반환한다.
'알고리즘 > 프로그래머스 JAVA LV.2' 카테고리의 다른 글
| 게임 맵 최단거리 (0) | 2023.05.30 |
|---|---|
| 오픈채팅방 (0) | 2023.05.30 |
| [1차] 뉴스 클러스터링 (0) | 2023.05.30 |
| 땅따먹기 (0) | 2023.05.29 |
| 더 맵게 (0) | 2023.05.29 |