[프로그래머스 k진수에서 소수 개수 구하기] c++ (풀이법,코드)

문제 링크

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

프로그래머스

 

문제

 

풀이 및 코드

저는 이 문제를 조금 다른 방법으로 접근하였습니다. 

문제에서의 0p혹은 p0 혹은 0p0 혹은 p라는 숫자들을 보고 통일성 있게 설정을 해줄 수 있지 않을까? 라는 생각을 먼저하였습니다.

 

그래서 처음 숫자를 k진법으로 변환을 한 후에 vector v에 담아 줬습니다.

v에서 맨앞과 맨 뒤에 0을 넣게 된다면 

통일성 있게 무조건 0p0이 될수 밖에 없다는 것을 착안해서 문제를 풀었습니다

0p -> 00p0 

p0 -> 0p00

0p0 -> 00p00

p -> 0p0 생각해보자면 결국 무조건 0에 둘러싸인 p가 될수 밖에 없다고 생각하였습니다.

 

그렇게 한후 0이 아닌 숫자들에 대해서 소수인지 아닌지를 판별한 후 계산을 진행해주었습니다.

 

또한 long long으로 하였을때 테스트1 에 대해서 틀렸길래 범위를 초과한 숫자가 들어왔나? 하고 unsigned long long으로 설정을 해주었더니 통과하였습니다.

#include <string>

#include <vector>

#include <iostream>

using namespace std;

bool isPrime(unsigned long long n)

{

    if (n <= 3)

        return n > 1;

    if (n % 2 == 0 || n % 3 == 0)

        return false;

    for (long long i = 5; i * i <= n; i++)

        if(n % i == 0)

            return false;

       

    return true;

}

int solution(int n, int k) {

    int answer = 0;

    int location = 1;

    unsigned long long num = 0;

   

    vector<int> v;

   

    //이런식이면 15면 210이 되야함

    while(n > 0){

        v.insert(v.begin(),n % k);

        n /= k;

    }

   

    //초반과 끝에 0을 넣어줌으로써 무조건 양옆에 0일경우에만 진행을 하는것으로 진행

    //굳이 split할 필요없이 0이 들어오면 무시하는 방향으로 그리고 양옆에 0이 꼭 있게 되는 상황으로 만들어줌

    v.insert(v.begin(),0);

    v.push_back(0);

   

    for(int i = 0; i < v.size();i++){

        if(v[i] == 0){

            if(isPrime(num))

                answer++;

            num = 0;

        }

        else{

            num *= 10;

            num += v[i];

        }

    }

    return answer;

}