프로그래머스 | Level 2 | k진수에서 소수 개수 구하기

Programmers | Level 2 | k진수에서 소수 개수 구하기

Problems

• 📘 Src: Programmers
• 🗂️ Cat: Math

Description

양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.

• 0P0처럼 소수 양쪽에 0이 있는 경우
• P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
• 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
• P처럼 소수 양쪽에 아무것도 없는 경우

단, P는 각 자릿수에 0을 포함하지 않는 소수입니다. 예를 들어, 101은 P가 될 수 없습니다.

예를 들어, 437674를 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.

정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.

Constraints

• 1 ≤ n ≤ 1,000,000
• 3 ≤ k ≤ 10

Examples

n	k	result
437674	3	3
110011	10	2

Solutions

• ⏳ TC: O(n)
• 💾 SC: O(n)

import java.util.*;

class Solution {
    
    public int solution(int n, int k) {
        String digit = Integer.toString(n, k);
        String[] digits = digit.split("0+");
        
        int count = 0;
        for (String ele : digits) {
            if(ele.isEmpty()) continue;
            if(isPrime(ele)) count++;
        }
        
        return count;
    }
    
    private boolean isPrime(String digit) {
        long number = Long.parseLong(digit);
        if (number <= 1) return false;
        if (number == 2 || number == 3) return true;
        if (number % 2 == 0 || number % 3 == 0) return false;
        
        for (long i = 3; i <= Math.sqrt(number); i += 2) {
            if (number % i == 0) return false;
        }
        
        return true;
    }
}

Approaches

이 문제는 주어진 숫자 n을 k진수로 변환한 후, 변환된 문자열에서 특정 조건에 맞는 소수를 찾아야 합니다. 변환된 문자열에서 소수는 양쪽에 0이 있거나, 한쪽에만 0이 있거나, 양쪽에 아무것도 없는 경우에 해당합니다. 각 소수는 0을 포함하지 않는다는 점에 유의해야 합니다. 이를 해결하기 위해 다음과 같은 단계로 접근합니다:

• 진법 변환:
  • 주어진 정수 n을 k진수 문자열로 변환합니다. 이는 Java의 Integer.toString(int number, int radix) 메서드를 사용하여 수행할 수 있습니다.
  • 변환된 k진수는 하나의 문자열로 표현됩니다. 예를 들어, n = 437674이고 k = 3일 때, n을 k진수로 변환하면 211020101011이 됩니다.
• 소수 후보군 추출:
  • 변환된 k진수 문자열을 0을 기준으로 분할하여 소수 후보군을 추출합니다. 이는 각 소수는 0을 포함하지 않는다는 조건에 따라 0을 기준으로 나눠야 하기 때문입니다.
  • 이 과정을 위해 0이 하나 또는 연속된 경우를 정규식 패턴 0+을 사용하여 처리합니다.
  • Java 내장 함수 String.split(String regex)를 사용하면 연속된 0도 하나의 기준으로 처리하여 문자열을 분할할 수 있습니다.
  • 예를 들어, 211020101011을 0을 기준으로 분할하면 ["211", "2", "1", "11"]이 됩니다. 이 분할된 각 조각은 독립적으로 소수 판별을 수행할 숫자 후보군입니다.
• 소수 판별:
  • 각 숫자 조각이 소수인지 확인합니다.
  • 10진법의 수를 다른 진법으로 변환하면 매우 큰 길이로 변환될 수 있기 때문에, 이 과정에서 큰 숫자를 다룰 수 있도록 long 타입을 사용합니다.
  • 숫자의 소수 판별은 다음과 같은 단계로 수행할 수 있습니다:
    • 1 보다 큰 경우에만 소수일 수 있습니다.
    • 숫자가 2 또는 3이면 소수입니다.
    • 4 이상의 숫자는 해당 숫자의 제곱근까지 어떤 수로도 나누어지지 않는지 확인해야 합니다.
  • 예를 들어, 211은 소수입니다. 2도 소수입니다. 1은 소수가 아닙니다. 11은 소수입니다. 따라서 소수는 211, 2, 11로 총 3개입니다.
• 결과 반환:
  • 소수인 숫자 조각의 개수를 카운트하여 반환합니다. 위의 예에서는 3이 반환됩니다.

이 알고리즘의 시간 복잡도는 O(n)이며, 공간 복잡도 또한 O(n)으로 효율적으로 문제를 해결할 수 있습니다.