k진수에서 소수 개수 구하기(2022 KAKAO BLIND RECRUITMENT)

문제

코드

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        StringBuilder s=new StringBuilder();
        int start,end;
        int index=0;
        while(n!=0){
            s.insert(0,n%k);
            n/=k;
        }     
        while(index<s.length()){
            if(s.charAt(index)!='0'){
                start=index;
                StringBuilder a=makeString(start,s);
                if(checkPrime(a)){
                    if(start-1<0) answer++;
                    else if(start+a.length()==s.length()) answer++;
                    else answer++;
                }
                index+=a.length();
            }
            else index++;
        }
        return answer;
    }
    public StringBuilder makeString(int start,StringBuilder s){
        StringBuilder a=new StringBuilder();
        while(start<s.length()&&s.charAt(start)!='0'){
            a.append(s.charAt(start));
            start++;
        }
        return a;
    }
    public boolean checkPrime(StringBuilder s){
        long num=Long.parseLong(s.toString());
        if(num==1) return false;
        else{
            for(int i=2;i<=(int)Math.sqrt(num);i++){
                if(num%i==0)
                    return false;
            }
        }
        return true;
    }
}

풀이

(1) 주어진 n을 k진수로 만들어준다.(StringBuilder 이용)
(2) k진수로 만든 StringBuilder을 한자리씩 확인하여 준다.
-> 0이 아닌 숫자가 나오면 makeString() 메소드를 통해 판별할 숫자를 받아온다.
-> 0이면 다음 숫자로 넘어간다.
(3) makeString()으로 받아온 숫자를 checkPrime() 함수를 통해 소수 판별을 해준다.
(4) 소수가 맞다면, 조건에 일치하는지 확인 후에 answer++을 해준다.

결과

처음에 내가 짠 코드에서는 자꾸 시간 초과가 나왔다. 그 이유는 소수를 판별할때 2~n까지의 수의 나머지를 하나씩 전부 계산했기 때문이다. 소수는 사실 n의 제곱근 까지만 나누어도 판별할 수 있다.

문제를 풀고 나서, 베스트 코드를 확인했더니 정말 간단하게 이 문제를 해결할 수 있다는 사실을 알게되었다.
먼저, n을 k진수로 바꾸는 과정을 직접 구현하지 않아도, Integer.toString(int i,int radix) 함수를 통해 간단히 할 수 있다는 것이다.
Interger.parserInt(String s,int radix)로 k진수를 10진수로 바꿀 수 있다는 사실은 알고 있었지만, 그 반대도 가능한 것은 처음 알았다.
그리고 문제에서 주어진 "P0"과 같은 조건은 그냥 k진수로 바꾼 수를 split("0")을 하면 자연스럽게 만족된다는 것도 알 수 있었다.

좀만 더 생각하면 일일이 구현하지 않아도 간단하게 만들 수 있는 코드들이라는 것이 아쉬웠다. 좀 더 스킬을 키울 필요가 있다.

출처 : 프로그래머스 코딩 테스트 연습 https://school.programmers.co.kr/learn/challenges