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

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

프로그래머스

---

❓ 문제

 

---

❕ 풀이

1. n을 k진수로 변환합니다.

2. k진수로 변환한 수를 0으로 split 하고, 각 수가 소수라면 answer ++ 합니다.

 

 

1. n을 k진수로 변환

저는 stack을 이용해서 풀었는데, 더 좋은 방법을 소개하겠습니다!

 

1) Integer.toString(int i, int radix)

public static String toString(int i, int radix)

 

Returns a string representation of the first argument in the radix specified by the second argument.

If the radix is smaller than Character.MIN_RADIX or larger than Character.MAX_RADIX, then the radix 10 is used instead.

 

If the first argument is negative, the first element of the result is the ASCII minus character '-' ('\u002D'). If the first argument is not negative, no sign character appears in the result.

The remaining characters of the result represent the magnitude of the first argument. If the magnitude is zero, it is represented by a single zero character '0' ('\u0030'); otherwise, the first character of the representation of the magnitude will not be the zero character. The following ASCII characters are used as digits:

0123456789abcdefghijklmnopqrstuvwxyz

These are '\u0030' through '\u0039' and '\u0061' through '\u007A'. If radix is N, then the first N of these characters are used as radix-N digits in the order shown. Thus, the digits for hexadecimal (radix 16) are 0123456789abcdef. If uppercase letters are desired, the String.toUpperCase() method may be called on the result:

Integer.toString(n, 16).toUpperCase()

Parameters:

i - an integer to be converted to a string.

radix - the radix to use in the string representation.

Returns:a string representation of the argument in the specified radix.

 

Java 문서에서 가져온 내용인데 10진수인 i를 radix 진수로 변환해주는 메소드입니다.

이 메소드를 사용하면 간단하게 n을 k진수로 변환할 수 있습니다.

String knum = Integer.toString(n, k);

 

2) StringBuilder 사용하기

n을 k로 나눈 나머지 값을 StringBuilder에 붙여가면서 n을 k로 나눠주고, StringBuilder를 reverse하면 됩니다.

StringBuilder sb = new StringBuilder();

while(n != 0){
    sb.append(n % k);
    n /= k;
}

String knum = sb.reverse().toString();

 

 

 

2. k진수로 변환한 수를 0으로 split 하고, 각 수가 소수인지 판별

 

앞에서 구한 k진수를 "0"으로 split 합니다.

String[] arr = knum.split("0");

 

이제 arr 배열에 있는 값이 소수인지 판별하면 됩니다.

 

"0"으로 split을 했기 때문에 knum에 "0"이 연달아 있으면 arr 배열에 "" 빈 문자열이 들어갈 수 있습니다.

각 수를 판별할 때 입력의 길이가 0보다 큰 지를 확인해야 합니다.

 

주의할 점은! 문제에서 n의 범위가 최대 1,000,000이기 때문에 k진수로 변환한 값이 int 형의 범위를 벗어날 수 있습니다. 그래서 arr[i]를 long 형으로 변환해야 합니다!

(처음에 이걸 모르고 계속 런타임 에러가 났었습니다 ..)

 

arr[i]의 길이가 0보다 크고 arr[i]가 소수라면 answer ++ 하면 됩니다.

for(int i=0; i<arr.length; i++){
    if(arr[i].length() > 0 && isPrime(Long.parseLong(arr[i]))){
        answer ++;
    }
}

 

 

소수인지 판별하는 isPrime 함수는 다음과 같이 구현했습니다.

public boolean isPrime(long k){
    if(k == 1){
        return false;
    }
    long a = (long)Math.sqrt(k) + 1;
    for(int i=2; i<a; i++){
        if(k % i == 0){
            return false;
        }
    }
    return true;
}

1은 소수가 아니기 때문에 입력이 1이라면 false를 return 하고

나머지 수는 2부터 자기 자신의 제곱근까지의 수로 모두 나눠 떨어지지 않는다면 소수이므로 true, 나눠 떨어지는 수가 있다면 소수가 아니기 때문에 false를 return 합니다.

 

소수를 판별하는 문제는 자주 나오니까 방법을 외워놓으면 좋을 것 같습니다!

 

---

소스코드

import java.util.*;

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        
        String knum = Integer.toString(n, k);
        
        String[] arr = knum.split("0");
        
        for(int i=0; i<arr.length; i++){
            if(arr[i].length() > 0 && isPrime(Long.parseLong(arr[i]))){
                answer ++;
            }
        }
        
        return answer;
    }
    
    public boolean isPrime(long k){
        if(k == 1){
            return false;
        }
        long a = (long)Math.sqrt(k) + 1;
        for(int i=2; i<a; i++){
            if(k % i == 0){
                return false;
            }
        }
        return true;
    }
}

 

---

마치며 ...

2진수로 바꾸는 문제는 몇 번 풀어봤는데 k진수로 바꾸는 문제는 처음이었다. 덕분에 Integer.toString이라는 유용한 메소드를 알 수 있었다.