[프로그래머스 JAVA] k진수에서 소수 개수 구하기 문제 풀이

 

지난번 어떤 기업의 코테를 보고 충격받아 한동안 문제풀이를 안하고 놀러갔다와버렸다 히히..

다시 마음을 다 잡고 공부 시작!! 

 

이번에는 k진수에서 소수 개수 구하기 문제 풀이를 해보겠다.

 

 

 

문제를 보곤 생각보다 간단한데? 라고 생각했다.

주어진 문자열을 주어진 수로 진수 변환하고 문자열 배열에 저장해서 소수인지만 확인하면 될 것 같았다.

 

String s = Integer.toString(n, k);
List<String> nums = new ArrayList<>(List.of(s.split("0")));

 

0을 제외한 값으로 배열을 만들어서 반복문을 돌렸는데, 런타임 에러가 떴다.. ㅠ 

서치를 해봤더니 nums의 값이 클수록 시간 복잡도가 증가하게 된 것이였다.

그래서 거진 소수 판별 알고리즘을 활용한다는 것을 봤다.

 

에라토스테네스의 체라고 하는 알고리즘은

2부터 주어진 값의 제곱근 이하만큼 반복문을 돌려 나누어 0이면 false를 반환하고 아니면 소수임을 확인했다는 것으로 true를 반환하는 방식이다. 

 

만약, 주어진 값이 50 이라면 약수는 1, 2, 5, 10, 25, 50 이 되는데 

50의 제곱근 =  7.071.... 보다 작은 약수 중 2 이상인 것부터 2, 5 만 소수인지 확인하면 된다는 것이다. 

이 알고리즘을 활용하면 전체 반복문을 돌리는 것보다 2배 정도 빠르게 실행 가능하다. 

 

여기서 제곱근은 Math.sqrt() 메소드를 활용하면 된다. 

최종 코드이다. 

import java.util.*;

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        String s = Integer.toString(n, k);
        List<String> nums = new ArrayList<>(List.of(s.split("0")));
        // System.out.println(nums);
        for (String str : nums) {
            // 빈 배열 제외
            if (str.equals("")){
                continue;
            }
            else if (check(str)) {
                answer++;
            }
        }
        return answer;
    }
    
    public static boolean check(String str) {
        boolean result = true;
        long n = Long.parseLong(str);
        // 1 제외
        if (n == 1) {
            result = false;
        }
        // 에라토스테네스의 체 알고리즘 > 소수 판별 
        for (int i=2; i<=Math.sqrt(n); i++) {
            if (n % i == 0) {
                 result = false;
            } 
        }
        return result;
    }
}

 

이렇게 했더니 결과가 성공적이었다.

대신 1은 따로 예외처리하였다.