[프로그래머스,자바] Level2: K진수에서 소수 개수 구하기

 

 

문제풀이

 

문제보고 한 5분동안 멍 때린 문제다....

 

처음 생각했을때,  문제 설명처럼 0P0 , 0P, P0, P인 경우를 모두 고려해서 뽑아야 하나 생각햇는데,

방법도 잘 떠오르지도 않으며 그냥 귀찮았다...

 

 

뭔가... 좀 쉽게 풀수는 없나 꼼수를 부리다가 이런 생각 해봤다.

 

그냥 이거 "0" 들어간걸 기준으로 분해시켜버리면 되는거아닌가??

 

생각해보니 4개의 기준 모두 0을 기준으로 분리가되어있고, 0을 기준으로 분해를해도 문제될게 전혀 없다는걸 발견했다.

 

문제를 풀기위한 첫번째 스텝으로 N진법 로직이다.

 

알고리즘 문제를 많이풀어봤으면 N진법 변환 로직은 간단하다. 

While문을 사용하여,  N을 K로 나눈 나머지를 계속 앞에다가 붙여가면된다.

 

 

두번째 스텝으로,  이 N진법으로 푼 문자열을 "0" 을 기준으로 Split을 한다.

 

이 과정을 거칠때 주의할 2가지가 있다.

 

첫번째, 빈칸이 생성이 될때가있다.

-> 1001 을 분해하면 1 , "" , 1이 반환이된다. 빈칸을 숫자로 변환하면 오류를 뱉으니 이런 경우는 제외해야한다.

 

두번째, 변환할때 숫자를 Long 타입으로 바꾸어야한다.

 

-> 필자가 놓친 MISS중 하나다. 이 과정을 거치지않으면 테스트케이스 1번 ,11번이 오류가난다.

-> 이 오류가 일어나는 이유는  최대 100만이라는 숫자를 N진법 변환을하면 엄청난 길이의 숫자로 나열되고,

int의 범위를 넘어서는 숫자가 생성되는 경우가 있기때문이다.

 

 

 

다음과같은 주의사항을 다 거치면 마지막 스텝으로 소수인지 판별하면 된다.

 

소수 판별 알고리즘도 꽤나 유명한 로직이다.

 

소수를 판별할때는 에라토네스 체를 사용하는걸 권장한다. 연산을 최대한 많이줄이면서 소수인지 판별이 가능하다.

 

https://taehoung0102.tistory.com/55

[프로그래머스,Java] Level1: 소수 찾기

 

 

문제분석

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;
    }
}