[코딩테스트] 프로그래머스 92335, k진수에서 소수 개수 구하기

문제

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

프로그래머스

 

문제접근

1. 십진수 n을 k진수로 변환
2. 문자열 타입으로 변환한 k진수 문자열을 0번째부터 탐색
3. 순회도중 i번째 값이 0이거나 문자열의 끝인 경우 조건에 맞는 부분을 추출합니다.
   
   1. 예를 들어 k진수 문자열이 "211020101011"인경우 추출되는 문자열들은 "2110", "020", "010", "010", "011"입니다.
4. 추출한 문자열을 십진수라고 가정하고 소수인지 판단합니다.
   1. 예를 들어 "2110" -> "211"로 변환되고 "211"은 3진수이지만 10진수 211라고 가정하고 소수인지 판단합니다.
5. 소수라면 카운팅하고 아니라면 다시 순회를 진행합니다.

 

구현

class Solution {
	public String convertFromDecimalToKNumber(int n, int k){
		StringBuilder sb = new StringBuilder();
		while(n != 0){
			sb.insert(0, n%k);
			n /= k;
		}

		return sb.toString();
	}

	public boolean isPrime(String k_num){
		String s = k_num.replace("0", "");
		s = s.equals("") ? "0" : s;

		long decimal = Long.parseLong(s);

		if(decimal <= 1){
			return false;
		}

		for(long i = 2; i*i <= decimal; i++){
			if(decimal % i == 0){
				return false;
			}
		}

		return true;
	}

	public int solution(int n, int k) {
		int answer = 0;
		String k_num = convertFromDecimalToKNumber(n, k);

		int start = 0;
		for(int i = 0; i < k_num.length(); i++){
			if(k_num.charAt(i) == '0' || i == k_num.length() - 1){
				String sub = k_num.substring(start, i+1);

				if(isPrime(sub)){
					answer++;
				}

				start = i;
			}
		}
		return answer;
	}

	public static void main(String[] args){
		//int answer = new Solution().solution(437674, 3);
		//int answer = new Solution().solution(110011, 10);
		//int answer = new Solution().solution(1, 3);
		int answer = new Solution().solution(1000000, 3);
		System.out.println(answer);
	}
}