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

문제

프로그래머스

 

알고리즘

없음

 

풀이

문제의 조건들은 전부 좌, 우에 아무것도 없거나 혹은 0이 있는 경우에 대한 조건들이다.

따라서 n을 k진수로 표현한 뒤 0을 기준으로 분리해 각 토큰 중 소수의 수를 세는 문제인 셈이다.

 

1. Integer.toString() 메소드를 이용해 n을 k진수의 문자열로 변환

2. StringTokenizer를 이용해 k진수 문자열을 "0"을 기준으로 분리

3. 토큰 중 소수의 수를 출력

---

소수 판별

소수는 1과 자기 자신만 약수로 가지는 수이다.

 

따라서  임의의 수가 소수인지 판별할 때

n이 2부터 n-1 까지 각 수로 나누어떨어지지 않는지 확인할 수 있다.

* 하지만 n-1 까지가 아니라 n의 제곱근까지만 확인해도 결과는 동일하다. 이를 통해 시간을 단축할 수 있다.

 

* 각 토큰이 9자리보다 커질 수 있으므로 long 자료형을 사용한다.

 

코드

import java.util.*;

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        String trN = Integer.toString(n, k);
        StringTokenizer st = new StringTokenizer(trN, "0");
        
        while(st.hasMoreTokens()) {
            String token = st.nextToken();
            if(check(Long.parseLong(token))) answer++;
        }
        return answer;
    }
    
    public boolean check(long n) {
        if(n == 1) return false;
        
        for(long i=2; i*i <= n; i++) {
            if(n % i == 0) return false;
        }
        return true;
    }
}