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

문제 풀이

---

이 문제는 정수를 진수로 변환하는 방법과 소수를 판별하는 알고리즘을 잘 숙지하고 있으면 쉽게 풀 수 있다.

아이디어 도출

1. 정수 n을 k진수로 변환한다.
2. 문자열로 변환된 k진수에서 0을 기준으로 분할한다.
3. 분할된 각 원소가 소수인지 확인하여 카운트한다.

위 아이디어대로 풀이방법을 자세히 살펴보자. 먼저 입력받은 정수 n을 k진수로 변환해야 한다.

Java에서는 Integer.toString() 메서드의 첫번째 인자로 변환할 정수, 두번째 인자로 변환할 진수값을 넣으면 정수를 원하는 진수로 변환할 수 있다.

다음으로 그렇게 k진수로 변환된 문자열을 String 클래스의 split() 메서드를 이용해 0을 기준으로 분할하여 배열로 만든다.

이후, 분할된 배열을 순회하면서 각 원소가 소수인지 확인하여 카운트를 세면 된다. 이때 각 원소가 소수인지 확인하기 위해서는 단순히 반복문을 통해 2부터 해당 수까지 반복하며 소수인지 확인하는 방법도 있지만, 시간 초과를 고려해야 하기 때문에 에라토스테네스의 체나 유클리드 호제법 알고리즘을 이용해야 한다.

이번에는 에라토스테네스의 체 알고리즘을 이용해 소수를 판별하는 로직을 이용하여 소수를 판별하도록 구현하였다.

에라토스테네스의 체 알고리즘을 활용해 소수를 판별하는 방법은 이전에 풀어봤던 신기한 소수 풀이에서 자세하게 확인할 수 있다.

작성 코드

---

import java.util.*;

class Solution {
    public int solution(int n, int k) {
        
        int answer = 0;
        String toBinaryString = Integer.toString(n, k);
        String[] str = toBinaryString.split("0");
        
        for(String s : str) {
            if(!s.equals("")) {
                long num = Long.parseLong(s);
                if(isPrime(num)) answer++;
            }
        }

        return answer;
    }

    // 소수 판별 메서드
    // 에라토스테네스의 체 알고리즘을 활용해 소수를 판별함.
    static boolean isPrime(long num) {
        int sqrt = (int)Math.sqrt(num);
        if(num == 0 || num == 1) {
            return false;
        }
        for(long i = 2; i <= sqrt; i++) {
            if(num % i == 0) return false;
        }   
        return true;
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        
        // int n = 437674;
        // int k = 3;
        // int n = 110011;
        // int k = 10;
        int n = 883438;
        int k = 3;

        sol.solution(n, k);
    }

}

회고

• ---

출처

- —

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.