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

potatoj11n·2024년 1월 31일

cpp 코딩테스트 프로그래머스

프로그래머스

목록 보기

18/25

🌱문제 설명

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

제한사항

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

입출력 예

n	k	result
437674	3	3
110011	10	2

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

110011을 10진수로 바꾸면 110011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 11, 11 2개입니다. 이와 같이, 중복되는 소수를 발견하더라도 모두 따로 세어야 합니다.

풀이

❣️ 문제 요약

입력받은 수 n을 k진수로 바꿔서 조건을 만족하는 소수를 찾는다.

🤔 생각해야할 점

입력받은 수를 주어진 진수로 바꿔줘야한다. (10진수에서 k진수로)

진수를 바꾸는 방법

n 이 0이 될 때까지 n을 k로 나누면서 나머지는 저장을 반복
저장된 나머지들을 reverse로 뒤집으면 k진수로 변환된다. ( 진수 변환 과정 )
string으로 바꾸어 return한다.

소수인지 판별해준다.
소수인 숫자 앞 뒤에 0이 있는지 확인

→ 0을 기준으로 수를 나눠서 소수인지 판별

#include <bits/stdc++.h>
using namespace std;

//바뀐 진수가 들어갈 문자열
string num;

//진수로 바꾸는 함수
void changenum(int& n, int& k) { // 인수를 참조로 전달!!
    while (n > 0) {
        num += to_string(n % k);
        n = n / k;
    }
    reverse(num.begin(), num.end());
}

//소수인지 확인
bool isPrime(long long num) { // 문자열로 받는 것이 아니라 정수로 받아야 합니다.
    if (num <= 1) // 1도 소수가 아닙니다.
        return false;
    for (long long i = 2; i * i <= num; i++) {
        if (num % i == 0)
            return false;
    }
    return true;
}

int solution(int n, int k) {
    int answer = 0;
    changenum(n,k);
    
    string check = "";//문자열 검사를 위해 빈 문자열 생성
    for (char c : num) { //문자열을 한단어씩 쪼개서 검사
        if (c == '0') { //0이면
            //문자열에 저장된 문자가 있고 소수이면
            if (!check.empty() && isPrime(stoll(check))) {
                answer++; 
            } 
            check = ""; //문자열을 다시 빈 상태로 만들어준다.
        } 
        else check += c; //0이 아니면 문자를 새 문자열에 저장
    }
    
    if (!check.empty() && isPrime(stoll(check))) {  //마지막꺼 
        answer++;
    } 

    return answer;
}

코드 설명

✅ n을 k진수로 바꾸는 코드

n 이 0이 될 때까지 n을 k로 나누면서 나머지는 저장을 반복
저장된 나머지들을 reverse로 뒤집으면 k진수로 변환된다. ( 진수 변환 과정)
string으로 바꾸어 return한다.

to_string 사용

string num;

//진수로 바꾸는 함수
void changenum(int& n, int& k) { // 인수를 참조로 전달!!
    while (n > 0) {
        num += to_string(n % k);//n을 k로 나눈 나머지를 문자열로 바꿔서 num에 저장
        n = n / k;//n을 n을 k로 나눈 몫으로 갱신하면서 0이 될때 까지 반복
    }
    reverse(num.begin(), num.end());//저장된 문자열을 거꾸로 읽어야 진수
}

✅ 0을 기준으로 문자열을 잘라서 소수인지 판별

문자열을 검사해서 새 문자열에 담는다.

예를 들어 문자열 num을 211020101011을 검사한다고 가정하면 새 문자열 check에 한 문자씩 2 , 1, 1 을 저장하다가 0인 문자가 나오면 그동안 저장되어 있던 211이 있는지 확인하고 그 211을 다시 숫자로 바꿔서 소수인지 검사해준다.

소수라면 answer 증가

⭐️ stoll 문자열 정수로 변환

int solution(int n, int k) {
    int answer = 0;
    changenum(n,k);
    
    string check = "";//문자열 검사를 위해 빈 문자열 생성
    for (char c : num) { //문자열을 한단어씩 쪼개서 검사
        if (c == '0') { //0이면
            //문자열에 저장된 문자가 있고 소수이면
            if (!check.empty() && isPrime(stoll(check))) {
                answer++; 
            } 
            check = ""; //문자열을 다시 빈 상태로 만들어준다.
        } 
        else check += c; //0이 아니면 문자를 새 문자열에 저장
    }
    
    if (!check.empty() && isPrime(stoll(check))) {  //마지막꺼 
        answer++;
  }

✅ 소수인지 판별해준다.( 바뀐 진수는 long long을 사용해 줘야함)

0,1은 소수가 아니다. 그리고 나누어 떨어지는 수가 있다면 소수가 아니다.

🍀소수판별 코드는 기억해두면 좋다

bool isPrime(long long num) { 
    if (num <= 1) //1은 소수가 아니니까
        return false;
    for (long long i = 2; i * i <= num; i++) {
        if (num % i == 0)//나누어 떨어지는 수가 있으면 소수가 아니다.
            return false;
    }
    return true;
}

🔥 추가

atoi , atol, atoll : 널 종료 문자열을 정수로 바꾼다.

stoul , stoull : 문자열을 부호 없는 정수로 바꾼다.

stof , stod , stold : 문자열을 부동 소수점 값으로 바꾼다.

to_string : 정수나 부동 소수점 값을 문자열로 바꾼다.

potatoj11n

이전 포스트

[프로그래머스]Lv.2 구명보트 - C++

다음 포스트

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