[C++] 프로그래머스 k진수에서 소수 개수 구하기

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

프로그래머스

풀이

정수 n과 k 가 주어졌을 때, n을 k 진수로 변환 후 주어진 기준에 따라 십진수로 변환 후 소수의 개수를 구하는 문제입니다.

문제를 3가지 파트로 나눠 구현합니다.

1. n을 k진수로 변환하기

convert(int n, int k) : while 문을 사용해 list 자료형에 나머지 값을 push_front 하면서 k진수 값을 저장합니다.

 

2. k진수를 10진수로 변환하기 

list 자료형을 순회하며 0이 아닌 값이 나올 때마다 vector 자료형에 push_back 해두고, 0이 나올 경우 십진수로 변환 후 소수판별 함수에 전달해줍니다. 소수 판별이 끝났다면 vector 자료형은 초기화합니다.

추가로, k진수의 마지막이 0이 아닌 경우가 있으므로 answer 리턴 전에 vector 자료형이 비어있지 않다면 한번 더 소수 판별을 해줍니다.

 

3. 10진수로 변환된 k진수를 소수인지 아닌지 판별하기

isprime(long long int n): 십진수로 변환된 k진수를 입력받아 소수를 판별하는 함수입니다. 이때, 10진수로 변환된 k진수 값이 int 형 범위를 넘어갈 수 있음에 유의하여 long long int로 인수를 전달 받습니다.

 

리뷰

n의 범위가 1,000,000이므로 k 진수를 10진수로 변환할 때 int형 자료범위를 벗어날 수 있음을 유의하자..!

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

using namespace std;
vector<int> v;
list<int> l;

void convert(int n, int k) {
    int rest = 0;
    while (1) {
        rest = n % k;
        n = n / k;
        
        l.push_front(rest);
        if (n == 0) break;
    }
    return; 
}

bool isprime(long long int n) {
    if (n == 1 || n == 0) return false;
   
    for (long long int i=2; i*i <= n; i++) {
        int rest = n % i;
        if (rest == 0) return false;
    }
    return true;
}

int solution(int n, int k) {
    int answer = 0;
    convert(n, k);
    
    for (auto i=l.begin(); i != l.end(); i++) {
        if (*i != 0) {
            v.push_back(*i);
        }
        else {
            long long num = 0;
            for (int j=0; j<v.size(); j++) {
                num += v[j] * pow(10, v.size() - j-1);
            }
            if (isprime(num)) answer++;
            v.clear();
        }
    }
    if (!empty(v)) {
        long long num = 0;
        for (int j=0; j<v.size(); j++) {
            num += v[j] * pow(10, v.size() - j-1);
        }
        if (isprime(num)) answer++;
    }
    return answer;
}