프로그래머스 lv.2 - 92335 k진수에서 소수 개수 구하기

프로그래머스 lv.2 - 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;
        String convertNum = Integer.toString(n, k);
        
        for(String s : convertNum.split("0", -1)) {
            if(s.length() == 0) continue;
            
            if(isPrimeNumber(Double.parseDouble(s))) {
                answer += 1;
            }
        }
        return answer;
    }
    
    private boolean isPrimeNumber(double n) {
        if(n <= 1) return false;
        
        double sqrt = Math.sqrt(n);
        for(int i = 2; i <= sqrt; i++) {
            if(n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

 

문제 해결 전략

이라 쓰고 문제를 보고서 어떻게 풀면 될까?에 대한 생각을 정리한 항목

처음 문제 설명의 'P'가 무슨 말이지? 싶었는데 알고보니 Prime number(소수)의 약자로 P를 사용하여 표현을 했던 것이었다.

이후 풀이는 입력 받은 n을 k진수로 변환 후 '0'을 기준으로 파싱하여 나온 수가 소수인지 판별만 하면 된다고 생각하였고, k진수로 변환하는 메서드가 있을 것 같아서 찾아보던 중 Integer 래퍼 클래스에 toString() 메서드에 해당 기능이 있음을 파악하여 쉽게 입력 받은 n을 k진수로 변환, 이 후 split() 메서드를 사용하여 파싱 후 나온 수가 소수인지 판별하여 카운트를 증가시켜 해결했다.

아무래도 진수 변환과 파싱에 대해 아는지 물어보는 문제가 아니었을까? 라는 생각을 한 문제였다.

 

---

코드를 업로드해 둔 깃 허브