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

문제 설명

양의 정수 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 함수를 완성해 주세요.

https://school.programmers.co.kr/learn/courses/30/lessons/92335?language=cpp 

프로그래머스

---

 

 

 

 

 

 

제한 사항

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

---

 

 

 

 

 

 

풀이

문제를 풀기 위해 두 가지 작업이 필요하다.

1. 주어진 n을 k진법의 수로 변환하는 것
2. 소수 판별

 

n을 k진법으로 변환하는 것은 재귀 함수로 간단하게 할 수 있다.

매개변수로 넘겨받은 n을 k로 나누면서 재귀를 진행한다. 

n이 k보다 작으면 준비한 vector에 저장한 뒤 return한다.

돌아와서는 n을 k로 나눈 나머지를 저장하면 된다.

이렇게 동작하는 이유는 n을 k로 나누며 재귀를 진행하기 때문에 재귀가 진행된다는 것은 k가 x번 곱해진다는 의미와 같다.

즉, 매개변수 n이 k보다 작아지는 경우는 수를 k진법으로 변환했을 때 제일 앞자리가 된다는 얘기이다.

이후, 돌아가면서 다음자리를 채워나가는 것이다.

vector<int> converted;

void Convert(int n, int k)
{
    if(n < k)
    {
        converted.push_back(n);
        return;
    }
    
    Convert(n/k, k);
    converted.push_back(n%k);
}

 

이렇게 변환한 수를 이용하여 패턴에 맞는 소수를 찾으면 된다.

소수를 찾는 방법은 간단하다.

2부터 n의 제곱근까지 나누어 떨어지는지 확인하면 된다.

제곱근까지만 확인해도 되는 이유는 나누어 떨어지는 수를 찾는 것이기 때문에 제곱근까지만 확인해도 곱으로 n을 만드는 모든 경우의 수를 확인할 수 있기 때문이다.

bool isPrime(long long n)
{
    if(n < 2) return false;
    
    for(long long i = 2; i <= sqrt(n); i++)
    {
        if(n%i == 0) 
        {
            return false;
        }
    }
    
    return true;
}

 

마지막으로 패턴에 맞는 수인지를 판단해야 한다.

패턴은 총 네 가지로 0P0, P0, 0P, P이다.

0P0, P0은 P가 0이 나오기 전까지의 수이다.

0P, P는 조회가 끝난 후, 남아있는 수이다.

이 두 가지 경우만 확인하면 된다.

for(auto c : converted)
{
	// 0이 나오면 확인
    if(c == 0){
        if(isPrime(temp))
        {
            answer++;
        }
        temp = 0;
    }
    // 아니면 채워 나가기
    else
    {
        temp *= 10;
        temp += c;
    }
}

// 남은 수 확인
if(isPrime(temp))
{
    answer++;
}

 

그리고 마지막으로 주의할 부분은 충분히 큰 수 n을 k진법으로 변한하면 int의 표현범위를 넘어가는 수가 생길 수 있다.

그래서 long long 자료형을 활용해야 한다.

---

 

 

 

 

 

전체 코드

#include <string>
#include <vector>
#include <iostream>
#include <cmath>

using namespace std;

vector<int> converted;

void Convert(int n, int k)
{
    if(n < k)
    {
        converted.push_back(n);
        return;
    }
    
    Convert(n/k, k);
    converted.push_back(n%k);
}

bool isPrime(long long n)
{
    if(n < 2) return false;
    
    for(long long i = 2; i <= sqrt(n); i++)
    {
        if(n%i == 0) 
        {
            return false;
        }
    }
    
    return true;
}

int solution(int n, int k) {
    int answer = 0;
    
    Convert(n, k);
    
    long long temp = 0;
	for(auto c : converted)
	{
		// 0이 나오면 확인
	    if(c == 0){
	        if(isPrime(temp))
	        {
	            answer++;
	        }
	        temp = 0;
	    }
	    // 아니면 채워 나가기
	    else
	    {
	        temp *= 10;
	        temp += c;
	    }
	}
	
	// 남은 수 확인
	if(isPrime(temp))
	{
	    answer++;
	}
    
    
    return answer;
}

---