[C#] 프로그래머스 LV.2 k진수에서 소수 개수 구하기

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

프로그래머스

 

주어진 수 n을 k진수로 변환한 후, 해당 조건에 맞는지에 따라 count를 세서 return해주는 문제이다.

 

잘 보면 0이 키워드인데 결국 0으로 해당 수를 나눠줘야 된다는 것이다.

 

진수변환

 

진수변환에는 String.ConvertTo(int32, int32); 로 진수를 변환시킬 수 있는데, 해당 문제를 ConverTo로 풀면 invaild Base 오류가 발생한다.

 

따라서 진수 변환을 직접 함수로 만들어서 계산해주면 된다.

 

그렇다면 어떤 식으로 생각해야 하는가?

 

진수 변환이라고 하면 예를들어 3진수라고 가정하면 3으로 나눈 나머지 가 진수가 되는데, number % 3 을 계속 해서 진수를 구할 수 있다.

 

10을 3진수로 바꾼다고 치면

• 10 % 3 = 1
• 10 / 3 = 3
• 3 % 3 = 0
• 3 / 3 = 1
• 1 % 3 = 1

이런 방식으로 101 이 3의 진수가 되어버린다. 

 

그렇다면 number % k 를 하여 number / k 를 하는 식을 number 가 0 이 될 때 까지 반복하면 된다는 뜻이다.

 

    public string CustomEssenceChange(int number, int k)
    {

        string chars = "0123456789";
        string result = "";


        while(number > 0)
        {
            result = chars[number % k] + result;
            number /= k;
        }

        return result == "" ? "0" : result;

    }

 

 

소수 계산

 

소수 계산은 0 과 1이 들어오면 소수가 아니기 때문에 거르고, 2부터 계산하는데  제곱근을 이용하여 i * i 로 최적화 하여 소수를 더 빠르게 판별하여 나누어 떨어지지 않으면 소수라고 판단하면 된다.

 

 public bool IsPrime(long number)
 {
     if (number < 2)
         return false;

     for(long i = 2; i * i <= number; i++)
     {
         if(number % i == 0)
             return false;
     }

     return true;

 }

 

 

이제 해당 함수들을 이용해 문제를 풀면 된다.

 

답

 

public class Solution
{
    public int solution(int n, int k)
    {
        string changeEssence = CustomEssenceChange(n, k);

        string[] parts = changeEssence.Split('0');

        int answer = 0;

        foreach(string part in parts ) 
        {
            if(!string.IsNullOrEmpty(part))
            {
                long number = long.Parse(part);
                if (IsPrime(number))
                    answer++;
            }
        
        }

        return answer;
    }
    
    public string CustomEssenceChange(int number, int k)
    {

        string chars = "0123456789";
        string result = "";


        while(number > 0)
        {
            result = chars[number % k] + result;
            number /= k;
        }

        return result == "" ? "0" : result;

    }

    public bool IsPrime(long number)
    {
        if (number < 2)
            return false;

        for(long i = 2; i * i <= number; i++)
        {
            if(number % i == 0)
                return false;
        }

        return true;

    }

    public static void Main(string[] args)
    {

        Solution s = new Solution();

        int n = 437674;
        int k = 3;


        int answer = s.solution(n, k);

        Console.WriteLine(answer);
    }
}