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

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

프로그래머스

 

1️⃣ 어떻게 문제를 풀까?

기본적으로 구현 문제라고 생각한다. 문제는 크게 2부분으로 나뉘어 지는데,

  1) 첫번째는 10진수를 k진수로 변환

  2) 두번재는 k진수에서 소수의 갯수를 구하는 것이다.

진수 변환은 단순히 n을 k로 나눈 후 나머지를 저장해서 구하면 된다! 이때 구해진 나머지를 역순으로 가져와야 하기 때문에 Stack 자료구조를 활용한다!

소수의 갯수를 찾는 것은 에라토스테네스의 체를 활용하면 된다! (관련 문제)

 

import java.util.*;

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        
        // n을 k진수로 바꾼다.
        String changed = toK(n, k);
        
        // 0을 기준으로 자른다.
        String[] nums = changed.split("0");
        for(String num : nums) {
            // 빈문자열은 skip한다.
            if(num.length() == 0) continue;
            
            // 소수인지 확인한다.
            if(isPrime(Long.parseLong(num))) {
                answer++;
            }
        }
        
        return answer;
    }
    
    private String toK (int number, int k) {
        Deque<Integer> stack = new ArrayDeque<>();
        
        while(number >= k) {
            stack.push(number % k);
            number /= k;
        }
        
        stack.push(number);
        
        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()) {
            sb.append(String.valueOf(stack.pop()));
        }
        
        return sb.toString();
    }

    // ❗ n의 최댓값 1_000_000을 3진수로 바꾼뒤 10진수로 보면 int범위를 초과함!
    private boolean isPrime(long number) {        
        if(number <= 1) return false;
        
        for(int i = 2; i <= Math.sqrt(number); ++i) {
            if(number % i == 0) {
                return false;
            }
        }

        return true;
    }
    
}

 

📌 처음 문제를 풀고 런타임 에러가 발생했다. n의 최댓값(1,000,000)을 3진수로 변환하면 가능한 가장 긴 수가 나오게 되고 이것은 1212210202001 이다. 소수를 구할 때 변환된 수(k진수)를 10진수처럼 보기 때문에 최종적으로 13자리(약 1조)의 수가 나올수도 있다. 그리고 당연하게 이는 int 범위(21억)을 벗어난다! 그래서 isPrime()의 매개변수를 int가 아닌 long으로 받아야 한다!

요즘 이런 숫자 범위를 자꾸 놓치는 것 같다.. 센스껏 데이터 타입에 유의하자!

📌 Stack은 레거시 자료형이기 때문에 Deque를 사용한다. (참고 자료)

📌 에라토스테네스의 체를 구현할 때 루트 number까지만 해도 된다!