[TIL] 프로그래머스) k진수에서 소수 개수 구하기 풀이 (Java)

 

학습 키워드: Java, long, int, overflow

 

문제 번호 - 문제 이름

1) 문제 설명 요약 (원문은 링크 참고):

 요약: 양의 정수 n을 k진수로 변환했을 때, P0, 0P0, 0P, 혹은 P 의 패턴으로 나타나는 소수 P의 개수를 찾아 반환하는 문제다.

 조건: 1 <= n <= 1,000,000, 3 <= k <= 10, 숫자 P는 0을 포함할 수 없음

 

2) 풀이 과정:

 문제를 좀 더 단순하게 풀어 설명하면, k진수로 변환된 숫자 n에 대해 0을 delimiter로 두고 분리시킨 숫자들이 소수인지를 판별하여 그 개수의 합을 구하는 것으로, 한 번에 풀어낸 적이 잘 없는 데이터 타입을 고려해야하는 유형의 문제다. 처음 문제를 읽었을 때는 예제에서 나온 211020101011의 케이스를 보면서 떠올린 방법인 최대 수를 찾아 그 미만의 소수를 미리 파악하는 방식으로 구현하고 86/100 점으로 실패했다.

 

 이후 문제를 다시 읽어보니 n이 백만이기 때문에 그 안의 어떤 수가 k진수로 변환됐을 때 int의 최대 크기를 넘어가는 0을 포함하지 않는 숫자가 있을 수도 있겠다는 생각을 했다. 그래서 숫자를 변환할 때 사용할 변수의 type을 long으로 설정하고 진행했으나, 88/100 점으로 한 개의 케이스를 더 해결하고 실패하게 되었다.

 

 원인은 바로 long 값을 설정하는 곱셈 계산에 int 값 들을 사용하는 바람에 생긴 overflow 였다.

// 실패한 코드

import java.lang.Math;

class Solution {
    public int solution(int n, int k) {
        int count = 0;
        long converted = 0;
        int mult = 1; // mult as int
        while (n > 0) {
            int cur = n % k; // cur as int
            n /= k;
            if (cur == 0) {
                if (isPrime(converted)) count++;
                converted = 0;
                mult = 1;
                continue;
            }
            converted += cur * mult;
            // int * int put into long, where calculation already overflowed
            mult *= 10;
        }
        
        if (isPrime(converted)) count++;
        
        return count;
    }
	
    ...
    
}

 

 

3) 정답 코드:

import java.lang.Math;

class Solution {
    public int solution(int n, int k) {
        int count = 0;
        long converted = 0;
        long mult = 1;
        while (n > 0) {
            long cur = n % k;
            n /= k;
            if (cur == 0) {
                if (isPrime(converted)) count++;
                converted = 0;
                mult = 1;
                continue;
            }
            converted += cur * mult;
            mult *= 10;
        }
        
        if (isPrime(converted)) count++;
        
        return count;
    }
    
    private boolean isPrime(long number) {
        if (number <= 1) return false;
        long sqrt = (long) Math.sqrt(number);
        for (long i = 2; i <= sqrt; i++) {
            if (number % i == 0) return false;
        }
        return true;
    }
}

 Java에서 숫자의 연산은 연산 내 가장 큰 버퍼를 가지는 타입을 따라간다고 한다. 이 코드에서 mult는 자릿수고, cur은 변환된 수의 일부분(n을 k로 나눈 나머지)인데, 사실 변환된 수 converted를 계산하는 과정에서 이 둘을 곱하는 것이 유일한 사용처여서 cur 값이 int여도 연산에 문제가 생기지 않기 때문에 메모리를 적게 사용하도록 int로 설정하는 것이 바람직하다.