[프로그래머스] k진수에서 소수 개수 구하기

https://school.programmers.co.kr/learn/courses/30/lessons/92335

프로그래머스

\

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

문제 설명

문제 설명

양의 정수 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 함수를 완성해 주세요.

 

(풀이코드) 

class Solution {
    public int solution(int n, int k) {
            int answer = 0;
	        long pn =0;
	        long t =1;
	        while(n>0) {
	        	if(n%k==0) {//맨뒤 0
	        		//소수검사
	        		boolean flag = true;
	        		if(pn==0||pn==1)flag = false;
	        		long p = (long)Math.sqrt(pn);
	        		for(long i = 2; i<=p; i++) {
	        			if(pn%i==0) {
	        				flag = false;
	        			}
	        		}
	        		if(flag || pn==2) {
	        			answer++;
	        		}
	        		pn=0;// 초기화
	        		t =1; 
	        	}else {
	        		pn += n%k*t  ;
	        		t*=10;
	        	}
	        	n/=k;
	        }
	        boolean flag = true;
    		if(pn==0||pn==1)flag = false;
    		long p = (long)Math.sqrt(pn);
    		for(long i = 2; i<=p; i++) {
    			if(pn%i==0) {
    				flag = false;
    			}
    		}
    		if(flag || pn==2) {
    			answer++;
    		}

	        return answer;
    }
}

(풀이코드)
이거 가지고 한참을 고민했다. 질문하기에 들어가서 보니까. 
소수를  찾아보니 2의 40제곱까지 변환하는데 long으로 해야 계산이 가능하다고 하였다. 
11,14,16 이렇게 틀렸었는데, 계속 틀리는게 위에 소수 계산 식만 바꾸고, 아래 꺼는 안바꿔서 계속 틀렸다..
앞으로.. 소수 계산할때는 Long을기본으로 쓰는 걸루....

그 부분말고는 코드는 단순하다. 

먼저

k진수 소수를 만들고 비교할 수 있는 코드를 위한 기본값들이다. pn이 소수를 저장할 수와, t는 자리수를 맞추기 위해 10의 자리수로 맞춰줄 수이다. 

다음코드는 k진수를 만들어서(pn) 이 수가 소수인지 확인한다. 
k진수를 만들때 몫과 나머지 방식으로 만들기 때문에 뒤에서 부터 계산하는데,  값들 이전에 문제 조건에 있었던 " 오른쪽에 아무것도 없는 경우" 에 포함되고, 그 이후의 값들은 찬찬히 비교하기 떄문에 계산이 된다. 
우선 0이 나올 경우 그 값까지만 계산하면 되기 때문에 n%k==0인 시점이 소수검사를 할 시점이 된다.

검사를 위해 flag라는 판단 변수를 하나 설정해 둔다. 그리고 pn이 0일경우나, 1일 경우는 소수가 아니므로 제외해준다.
그리고 소수 검사를 위해 p라는 """LONG""" 값을 설정해준다. 이 값은 비교의 편의를 위해 Math.sqrt로 루트값을 구해서 계산한다. pn%i 가 0이란건 나누어 떨어진다는 의미이므로 소수가 아니다. 따라서 flag를 false로 설정해준다. 
아니라면 i를 2부터 나누어 줬으나, 2거나 flag가 true라면 소수이므로 answer의 값을 +1 해준다.

그리고 나서 이제 소수인 pn은 초기화하고 자릿수 변환에 이용할 t도 1로 초기화해준다.