[프로그래머스] LEVEL2 k진수에서 소수 개수 구하기 JAVA

k진수에서 소수 개수 구하기

문제링크

문제 설명

양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.

• 0P0처럼 소수 양쪽에 0이 있는 경우
• P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
• 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
• P처럼 소수 양쪽에 아무것도 없는 경우
• 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
  • 예를 들어, 101은 P가 될 수 없습니다.

정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.

풀이

1. 양의 정수 n을 k으로 바꿉니다. Integer.toString(n, k);
ex) n = 437674, k=3
numStr = "211020101011"이 저장됩니다.
2. 위 문제 설명에 맞는 조건을 찾기 위해서는 위 numStr를 0으로 split하여 P를 찾아야한다고 생각했습니다.
   String[] split = ["211", "2", "1", "1", "11"]를 얻을 수 있습니다.
3. 해당 P 숫자들에 대해 소수가 맞는 지 확인하는 과정을 거칩니다.
   • 단, 예외 처리를 위해 00이 붙어 있어서 split에 ""가 들어있는 경우는 확인하지 않습니다.
   • 해당 split[i]번째 숫자를 long 형태로 변환 후 isPrime(num)함수로 소수가 맞는지 확인합니다. 만약 소수가 맞다면 answer++로 개수를 셉니다.
   • 추가로, 소수가 확인된 숫자의 경우 set에 추가합니다. 이후 split에서 나온 숫자가 set에 이미 존재한다면, 숫자가 이전에 이미 isPrime을 확인하여 조건을 만족하는 소수임으로 isPrime 함수를 호출하지 않고 answer++;를 해줍니다.
4. answer 리턴을 통해 조건에 맞는 소수의 개수를 얻을 수 있습니다.

코드

import java.util.Arrays;
import java.util.HashSet;

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        
        String strNum = Integer.toString(n, k);
        String[] split = strNum.split("0");
        
        HashSet<Long> set = new HashSet<>();
        
        for (int i = 0; i < split.length; i++) {
            
            if (split[i].equals("")) continue;
            
            long num = Long.parseLong(split[i]);
            
            if (set.contains(num)) {
                answer++;
            } else {
                if (isPrime(num)) {
                    answer++;
                    set.add(num);
                }
            }
        }
        return answer;
    }
    
    private boolean isPrime(long num) {
        
        if (num == 1L)
            return false;
        
        for (long i = 2L; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}