[알고리즘] K진수에서 소수 개수 구하기

양현지·2024년 6월 16일

알고리즘

목록 보기

26/27

※ 문제 출처 : 프로그래머스 k진수에서 소수 개수 구하기 lv2.

1. 개요

1) 문제 개요

2) 입출력 형식

3) 제한 사항

2. Solution I.

1) 알고리즘 개요

① N -> K 진수 변환 함수 작성

출력 형식 : vector

예시 :
17(N) -> 3(K)진수 변환
17 / 3 = 5 ...1
5 / 3 = 1 ...2
2
=> 122 ( 9 + 2 X 3 + 2)

② 소수 판별 함수 작성

출력 형식 : bool
2~n의 제곱근 사이의 정수와 나눠 떨어지는 값이 있으면 -> false/ 없으면 -> true

③ K진수 소수 판별

OPO PO OP P CASE

// https://school.programmers.co.kr/learn/courses/30/lessons/92335
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
vector<int> makeKno(int n, int k)
{
  vector<int> no;
  while (n > k)
  {
      no.push_back(n % k);
      n /= k;
  }
  if (n == k)
  {
      no.push_back(1);
      no.push_back(0);
  }
  else
      no.push_back(n % k);
  reverse(no.begin(), no.end());
  return no;
}

// ver 1. 2~ n-1 정수 중에 나눠 떨어지는 정수 존재 -> false/ else -> true
// 시간복잡도 : O(n) 
bool isPrime1(int n)
{
  for (int i = 2;i < n;i++)
      if (n % i == 0) return false;
  return true;
}

// ver2. 2~ n의 제곱근 중에 나눠 떨어지는 정수 존재 -> false/ else -> true
// 시간복잡도 : O(√N)
bool isPrime2(int n)
{
  if (n == 1) return false;
  for (int i = 2;i <= sqrt(n);i++)
      if (n % i == 0) return false;
  return true;
}


bool isPrime(vector<int>no)
{
  int number = 0;
  // 1. vector -> 10진수 정수
  for (int i = 0;i < no.size();i++)
      number += (no[i] * pow(10, no.size()-i-1));
  // 2. 소수 판별
  if (isPrime2(number)) return true;
  else return false;
}
int solution(int n, int k)
{
  int answer = 0;
  vector<int> number;
  number = makeKno(n, k);
  string str = "";
  for (int i = 0;i < number.size();i++)
  {
      if (number[i] != 0)
      {
          str += (number[i] + '0');
          if (i == number.size() - 1)
          {
              if (!isPrime(makeKno(stoi(str), 10))) continue;
              if (i - str.length() >= 0)
                  if (number[i - str.length()] == 0 && isPrime(makeKno(stoi(str),10))) answer++; // OP CASE
              // P CASE 
              if (str.length() == number.size()) answer++;
          }
      }
      else
      {
          if (str != "")
              if (isPrime(makeKno(stoi(str), 10)))            // 10진수 변환(P)
                  if (i - str.length() == 0) answer++;  // P0 CASE
                  else if (number[i - str.length()-1] == 0) answer++; //0P0 CASE

          str = "";
      }
  }

  return answer;
}

int main()
{
  solution(437674,3);
  return 0;
}