k진수에서 소수 개수 구하기

문제는 생각보다 쉬웠다. 완전탐색으로 풀수도있지만 조건을 잘 보면, 그냥 0으로 스플릿해서 스플릿된걸 소수인지아닌지만 판별하면 되는거였다. 그래서 1트에 어떻게 풀었는지 설명을 해보겠다.

 

 

ㅇ 1트

몇진수로 바꿔라 하는 k는 10이면 Integer.toString(n) 을써서 그냥 int를 String으로 그대로 바꿔줬고, 10이 아닌경우에는 k진수로 바꿔주는 Integer.toString(n,k)를 썼다.

cnt는 0을 기준으로 슬라이싱하고 각 원소들이 소수이면 갯수를 세도록 만들었고,

cntN는 String a (n을 k진수화한거) 자체가 0이없는 소수일경우에, 0이 있는지 없는지를 세기 위해 만들었다.

num은 a를 다시 Long형으로 바꾼거고,

a를첨부터 끝까지 돌면서 0이 있으면 cntN++ 해준다.

cntN 이 0인경우는 a에 0 이없다는소리고, num을 소수인지 판별했을때, 소수면 cnt++해줬다.

그다음에, 0을기준으로 parts 배열에 넣은뒤,

00이 붙어있으면 0과0사이에 ""가 들어가므로 ""를 다시 빼줘야해서(110011이면, "11", "" , "11"이되므로)

nonEmptyParts에 한번 넣어주고 ""를 빼서 각 원소를 long pa로 만들고 소수 검증을 해서 cnt++해줬다.

isPrime 함수는 각 원소가 1이하면 소수가 아닌걸로 치고, 제곱근을 사용해 소수 검증을 했다.

class Solution {
    public int solution(int n, int k) {
        //n을 k진수로 변환한다 예시) 437674, 3 일때 a는 211020101011
        //10진수로 변환할때는 n을 그냥 String으로 바꾼다.
        String a;
        if (k == 10) {
          a = Integer.toString(n);
        } else {
            a = Integer.toString(n, k);
        }
        int cnt = 0;
        int cntN = 0;
        //P 처럼 소수 양쪽에 아무것도 없는 경우 cnt 1추가
        long num = Long.valueOf(a);
            for (int j = 0; j < a.length(); j++) {
                if (a.charAt(j) == '0') {
                    cntN++;
                }
            }

            if (cntN == 0) {
                if (isPrime(num) == 1) {
                    cnt++;
                }
            }
            //0을 구분자로 문자열 슬라이싱
            String[] parts = a.split("0");
        ArrayList<String> nonEmptyParts = new ArrayList<>();

        for (String part : parts) {
            if (!part.isEmpty()) {
                nonEmptyParts.add(part);
            }
        }

        for (String part : nonEmptyParts) {
            long pa = Long.valueOf(part);
            if (isPrime(pa) == 1) {
                cnt++;
            }
        }
            return cnt;
        }


    //소수판별메서드. 소수면 1반환
    public static long isPrime(long n) {
        if(n <= 1){
            return 0;
        }
        for (int i = 2; i<=(int)Math.sqrt(n); i++) {
            if (n % i == 0) {
                return 0;
            }
        }
        return 1;
    }
}

절망...

 

ㅇ 2트

다시 정리하면서 보니, a 자체가 소수인경우에는 cnt++해줄필요가 없었다. 0을 기준으로 슬라이싱할때, 0이없으면 parts 배열에 a가 그대로 들어가기 때문이었다. 그래서 그부분을 주석처리하니 바로 성공해버렸다.

정말 바보같다.

class Solution {
    public int solution(int n, int k) {
        //n을 k진수로 변환한다 예시) 437674, 3 일때 a는 211020101011
        //10진수로 변환할때는 n을 그냥 String으로 바꾼다.
        String a;
        if (k == 10) {
          a = Integer.toString(n);
        } else {
            a = Integer.toString(n, k);
        }
        
        int cnt = 0;
        
        //P 일경우
        // long num = Long.valueOf(a);
        //     for (int j = 0; j < a.length(); j++) {
        //         if (a.charAt(j) == '0') {
        //             cntN++;
        //         }
        //     }
        //     if (cntN == 0) {
        //         if (isPrime(num) == 1) {
        //             cnt++;
        //         }
        //     }
            //0을 구분자로 문자열 슬라이싱
            String[] parts = a.split("0");
        ArrayList<String> nonEmptyParts = new ArrayList<>();
		//""를 parts에서 빼서 nonEmptyParts에다가 넣는다.
        for (String part : parts) {
            if (!part.isEmpty()) {
                nonEmptyParts.add(part);
            }
        }
		//nonEmptyParts에서 하나씩 소수검증 진행.
        for (String part : nonEmptyParts) {
            long pa = Long.valueOf(part);
            if (isPrime(pa) == 1) {
                cnt++;
            }
        }
            return cnt;
        }


    //소수판별메서드. 소수면 1반환. 1이하는 소수로 안침
    public static long isPrime(long n) {
        if(n <= 1){
            return 0;
        }
        for (int i = 2; i<=(int)Math.sqrt(n); i++) {
            if (n % i == 0) {
                return 0;
            }
        }
        return 1;
    }
}

소수판별하는 메서드인 isPrime은 정말 자주쓰이니깐 꼭 외워두는게 좋겠다.

 

ㅇ 다른사람들의 풀이

class Solution {
    public int solution(int n, int k) {

        int ans = 0;
        String temp[] = Integer.toString(n, k).split("0");

        Loop : for(String t : temp) {
            if(t.length() == 0) continue;
            long a = Long.parseLong(t);
            if(a == 1) continue;
            for(int i=2; i<=Math.sqrt(a); i++)
                if(a%i == 0) continue Loop;

            ans++;
        }
        return ans;
    }
}

이 풀이 외에도 다른 많은 분들도 isPrime 메서드를 사용해 푼걸 볼 수 있다.

이분은 정말 간결하게 잘 짜신거같다. temp[]에다가 n을 k진수로 바꾸고 0기준으로 스플릿도 했다.

그러고 ""일때는 continue 로 넘어가고, Long.parseLong(t)로 t를 long형 a로 바꾸고, a가 1인경우는 continue로 넘어가고,

반복문을 돌면서 소수검증을 진행했다. 내 코드와 로직은 같지만, 진짜 간결하게 잘짰다. 나도 이렇게 짜고싶다.