k진수에서 소수 개수 구하기
문제
https://school.programmers.co.kr/learn/courses/30/lessons/92335 (opens in a new tab)
내 풀이
내가 틀린 원인 분석
- 어떠한 문제의 조건에 대해서 그게 어떤 의미인지 파악하는 것을 너무 못했다.
- 예를 들어서, 지금 이 문제에선 결국 0사이에 있는 0을 포함하지 않는 문자이거나 양 끝에 있는 0을 포함하지 않는 문자를 찾아내는 것이 문젠데 이걸 한 줄로 요약하면 0으로 분리한 모든 문자열이다. 이걸 파악을 못했다.
- 에스토스테네
class Solution {
public int solution(int n, int k) {
int answer = 0;
// k 진수 String으로 변환
ArrayDeque<Integer> stack = new ArrayDeque<>();
while (n != 0) {
stack.addLast(n % k);
n /= k;
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pollLast());
}
String cw = sb.toString();
int cwLen = cw.length();
int start = -1;
int end = -1;
boolean ended = true;
for (int i = 0; i < cwLen; i++) {
if ((cw.charAt(i) == '0' || i + 1 == cwLen) && start != -1) {
end = i;
if (i + 1 == cwLen) {
end = i + 1;
}
String temp = cw.substring(start, end);
if (!checkPrime(temp)) {
start = -1;
end = -1;
ended = true;
} else {
answer++;
start = -1;
end = -1;
ended = true;
}
}
if (cw.charAt(i) != '0' && ended) {
start = i;
ended = false;
}
}
return answer;
}
public boolean checkPrime(String s) {
if (s.equals("1")) {
return false;
}
Long j = Long.parseLong(s);
for (long i = 2; i < j - 1; i++) {
if (j / i == 0.) {
return false;
}
}
return true;
}
}풀이
import java.util.*;
class Solution {
public int solution(int n, int k) {
int answer = 0;
String temp="";
//N진법 변환
while(n!=0){
temp=n%k+temp;
n/=k;
}
String[] arr = temp.split("0");
for(String data: arr){
if(data.equals("")) continue;
long num=Long.parseLong(data);
if(isPrime(num)){
answer++;
}
}
return answer;
}
//소수확인 메소드
public boolean isPrime (long a){
if(a<2) return false;
for(int i=2;i<=Math.sqrt(a);i++){
if(a%i==0){
return false;
}
}
return true;
}
}