[프로그래머스] k진수에서 소수 개수 구하기(Lv.2) - Java/자바

문제

링크

코딩테스트 연습 > 2022 KAKAO BLIND RECRUITMENT > k진수에서 소수 개수 구하기 (Lv. 2)
정답률 59% (2023.05.18 기준)

 

문제 설명

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

 

제한사항

• 1 ≤ n ≤ 1,000,000
• 3 ≤ k ≤ 10

 

입출력 예

n	k	result
437674	3	3
110011	10	2

 

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

 

입출력 예 #2

110011을 10진수로 바꾸면 110011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 11, 11 2개입니다. 이와 같이, 중복되는 소수를 발견하더라도 모두 따로 세어야 합니다.ㅇ

 

 

풀이

진법 변환과 소수 판별법에 관한 문제이다.

 

자바의 경우 진법 변환을 직접 구현할 필요가 없고.. java.lang.Integer 패키지에서 제공하는 Integer.toUnsignedString(int i, int radix) 함수를 쓰면 간단히 진법 변환을 한 문자열을 구할 수 있다. 여기서 i에는 10진수 숫자를 넣고, radix에는 변환하고자 하는 진법 수를 적으면 된다. 예를 들어 Integer.toUnsignedString(1234, 3)은 10진수 숫자 1234를 3진수로 변환한 문자열을 리턴한다.

 

소수 판별 알고리즘은 에라토스테네스의 체를 사용하지 않고 단순 알고리즘을 사용하였는데, 여기서 주의할 점은 2부터 number까지 for문을 돌며 검사하는 게 아니라, 2부터 number의 제곱근까지만 검사해야 한다는 것이다. number까지 검사하나, Math.sqrt(number)까지 검사하나 결과는 동일한데 number까지 다 돌게 되면 그만큼 시간이 더 걸리고.. 이 문제의 경우 number까지 다 돌리면 테스트 1번에서 오류가 난다! 항상 효율성 측면도 신경써서 문제를 푸는 습관을 길러야 할 것이다.

 

코드

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        
        String converted = Integer.toUnsignedString(n, k);
        String[] arr = converted.split("0");

        for(int i=0;i<arr.length;i++) {
            if(!"".equals(arr[i]) && isPrime(arr[i])) answer++;
        }
        return answer;
    }
    
    // 소수 판별 함수
    private static boolean isPrime(String s) {
        long number = Long.parseLong(s);
        if(number < 2) return false;
        
        for(int i=2;i<=Math.sqrt(number);i++) {
            if(number%i == 0) return false;
        }
        return true;
    }
}

 

해결 과정

1. 소수 판별 함수 isPrime을 정의한다.
   • 이 문제의 경우, k진수로 변환한 값이 문자열이고, 해당 문자열을 split한 부분 문자열이 소수인지를 판단해야 하므로 편의성을 위해 isPrime의 인자를 String으로 받아서, 함수 내에서 long으로 변환을 진행했다.
   • int로 변환 시 일부 테스트 케이스에서 런타임 에러가 발생하므로 long으로 변환해야 함에 주의한다.
   • 0, 1은 소수가 아니므로 false를 리턴한다.
   • 2부터 number의 제곱근까지, number를 나눈 나머지가 0인 값이 있는 경우 false를 리턴한다.
   • 그 외의 경우 true를 리턴한다.
2. 정수 n을 k로 변환한 문자열을 converted에 저장한다.
3. 소수의 조건을 다시 한번 살펴보면, k진수로 변환된 문자열을 "0"을 기준으로 split해서 각 부분문자열이 소수인지를 판별해야 하는 것임을 알 수 있다.
   
   문자열을 0을 기준으로 split하면 문제에서 제시했던 P0, 0P0, 0P를 모두 얻을 수 있다. P0의 경우 맨 처음 부분 문자열, 0P는 맨 마지막 부분 문자열, 0P0은 그 사이에 있는 부분 문자열이 될 것이다.
   
   그러므로 converted를 "0"을 기준으로 split한 배열을 arr[]에 저장한다.
4. 배열의 각 원소가 10진수로 했을 때 소수라면, answer에 1을 더한다. 배열 내 소수가 중복되어도 따로 카운트하면 되므로 단순히 소수 발견 시 1을 더하면 된다.
   1. 여기서 주의해야할 점은 원소가 빈 문자열인지부터 검사해야 한다는 것이다. 예를 들어 "110011"같은 문자열은 "0"을 기준으로 split하면 ["11", "", "11"] 이 되어 중간에 빈 문자열이 들어가게 된다. 빈값은 제외하고 소수 여부를 판별한다.
5. 최종적으로 구해진 answer값을 리턴한다.

 

 

실행 결과