문제

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

핵심

• 입력의 크기가 1,000,000이라 대략 $O(N*logN)$이하 알고리즘을 사용한다.
• 양의 정수 n이 주어지고, 이 숫자를 k진수로 변환해야 한다. 변환된 수 안에 소수가 몇 개인지 구해야 한다. 예를 들어, 437674을 3진수로 바꾸면 211020101011 이고 문제에 제시된 규칙에 따라 각 자릿수에 0이 포함되지 않은 소수의 개수를 구해야 하므로 211, 2, 1, 1, 11 숫자가 소수인지 판별하고 개수를 구하면 (211, 2, 11)로 3이 나온다.
• 문제를 풀기 위한 작업은 크게 3단계로 나뉜다.
  1. 진법 변환 하기
  2. 변환된 수에서 소수로 판별할 숫자 찾기
  3. 소수 판별 알고리즘

1. 진법 변환

• 진법 변환을 할 때 stack에 담아서 꺼내도 되지만, 코드가 더 길어진다. 진법 변환 수를 string에 담고, reverse를 해주었다.

string convert_base(int n, int k) {
    
    string base = "0123456789";
    
    if (n == 0)
        return "0";
    
    string ans = "";
    while (n > 0) {
        ans.push_back(base[n % k]);
        n /= k;
    }
    
    reverse(ans.begin(), ans.end());
    return ans;
}

• 만약에 16진수까지 변환할 수 있다면 어떻게 해야 할까? base 배열을 string base = "0123456789ABCDEF" 이런 식으로 수정하면 된다.

2. 소수로 판별될 숫자 찾기

• 소수로 판별할 숫자에 0이 있으면 안 되므로 0을 경계로 본다. 즉, 변환된 숫자를 순회하며 숫자 0을 만나면 이제까지 읽은 문자열을 숫자로 변환하고 다시 저장된 문자를 "0"으로 초기화한다.

void find_nums(string& converted) {
    
    string num = "0";
    for (int i = 0; i < converted.length(); ++i) {
        if (converted[i] == '0') {
            nums.push_back(stol(num));
            num = "0";
            continue;
        }
        num += converted[i];
    }
    nums.push_back(stol(num));
}

• 여기에서 놓쳤던 부분은 해당 숫자가 int에 담긴다고 생각했던 부분이다. 아래와 같이 n이 1,000,000이 넘지 않아도 변환된 문자열에선 int보다 큰 수가 나올 수 있다.
  

3. 소수 찾기 알고리즘

• 아리토스테네스의 체를 이용하면 더 빠르지만, 제곱근까지 검사해도 충분히 통과된다.

bool is_prime(long long num) {
    
    if (num <= 1)
        return false;
    
    if (num == 2) 
        return true;
    
    for (int i = 3; i <= num / i; ++i) {
        if (num % i == 0) return false;
    }
    
    return true;
}

개선

• 자바의 경우 아래와 같이 소수로 판별할 숫자를 toString과 split을 이용해 바로 구할 수도 있다.

String tmp[] = Integer.toString(n, k).split("0");

코드

C++

Java

import java.util.*;

class Solution {

    private List<Long> nums = new ArrayList<>();

    private boolean isPrime(long num) {
        if (num <= 1)
            return false;
        
        if (num == 2) 
            return true;
        
        for (long i = 3; i <= num / i; ++i) {
            if (num % i == 0) return false;
        }
        
        return true;
    }

    private void findNums(String converted) {
        StringBuilder num = new StringBuilder("0");
        
        for (int i = 0; i < converted.length(); ++i) {
        
            if (converted.charAt(i) == '0') {
                nums.add(Long.parseLong(num.toString()));
                num.setLength(0);
                num.append("0");
                continue;
            }
            num.append(converted.charAt(i));
        }
        nums.add(Long.parseLong(num.toString()));
    }

    private String convertBase(int n, int k) {
        String base = "0123456789";
        
        if (n == 0)
            return "0";
        
        StringBuilder ans = new StringBuilder();
        while (n > 0) {
            ans.append(base.charAt(n % k));
            n /= k;
        }
        
        return ans.reverse().toString();
    }

    public int solution(int n, int k) {
        String converted = convertBase(n, k);
        
        findNums(converted);
        
        int ans = 0;
        for (long e : nums) {
            if (isPrime(e)) {
                ++ans;
            }
        }
        return ans;
    }
}