[PS] Programmers - k진수에서 소수 개수 구하기

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

프로그래머스

 

 

◎ 문제풀이 

 

n = > k진수로 바꾸었을때, 구분자 0으로 구분되는 소수P의 개수를 구하는 문제이다. 이를 3가지 단계로 나누어 보았다.

1. k진수로 바꾸라.
2. 구분자 0으로 분리하라.
3. 소수 여부를 확인하라. 

 

주의)

K진수 안의 십진수를 정수로 변환할 때, Integer 범위를 넘을 수 있으므로 Long 자료형을 사용한다. 

 

◎ 코드

import java.util.*;
import java.io.*;

class Solution {
    public int solution(int n, int k) {
        
        //1. k진수로 바꾸라. ( Stack )
        Stack<Integer> stack = new Stack();
        
        while( n > k ){
            int r = n%k;
            n = n/k;
            stack.push(r);
        }
        stack.push(n);
        
        //2. 구분자 0으로 분리해라. 
        List<Long> ansList = new ArrayList();
        String result = "";
        while(!stack.isEmpty()){
            int value = stack.pop();
            
            if(value == 0){
                //3. 소수 검사 후 소수 저장하기 
                if(result!=""&&isPrime(Long.parseLong(result))){
                    ansList.add(Long.parseLong(result));
                }
                result = "";
                
            }else{
                result = result.concat(value+"");
            }
        }
        
        // 마지막 result가 존재하면 검사하기
        if(result!=""&&isPrime(Long.parseLong(result))){
            ansList.add(Long.parseLong(result));
        }
        
        //4. 결과 출력하기
        return ansList.size();

    }
    
    // 소수 여부 판별 
    public boolean isPrime(long value) {
        if(value == 1) return false;
        for(int i=2; i<=(int)Math.sqrt(value);i++){
            if(value%i == 0) return false;
        }
        return true;

    }
}