문제
양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.
- 0P0처럼 소수 양쪽에 0이 있는 경우
- P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
- 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
- P처럼 소수 양쪽에 아무것도 없는 경우
단, P는 각 자릿수에 0을 포함하지 않는소수입니다.
예를 들어, 101은 P가 될 수 없습니다.
입출력 예
문제 풀이
총 3단계에 나눠서 코드를 작성하면 어렵진 않은 것 같다.
1. 10진수 -> n진수로 바꾸기
2. 소수인지 판별하기
3. 소수인 숫자의 앞 뒤에 0이 있는지 확인하기.
🎈앞이나 뒤, 앞뒤 모두 0이 있는 경우가 소수인데 처음에는 세가지를 전부 따져줘야 하나 고민했다. 하지만 이 조건들은 결국 앞이나 뒤에 0이 하나라도 있으면 조건에 충족하는 경우이기 때문에 0을 기준으로 split를 하고 소수인지 판별하면 된다.
☝🏻 10진수 -> n진수 바꾸기
string s = "";
while(n > 0) {
s += to_string(n % k);
n /= k;
}
reverse(s.begin(), s.end());*거꾸로 다시 바꿔줘야하기 때문에 reverse를 사용
✌🏻 소수 판별 코드
bool isPrime(long long num) {
if(num < 2) return false;
for(int i=2; i<=sqrt(num); ++i) {
if(num % i == 0) return false;
}
return true;
}*소수 판별 코드는 많이 나오니 외워두는 게 좋다!
🤟🏻0을 기준으로 나눠주기(전체코드)
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
bool isPrime(long long num) {
if(num < 2) return false;
for(int i=2; i<=sqrt(num); ++i) {
if(num % i == 0) return false;
}
return true;
}
int solution(int n, int k) {
int answer = 0;
vector<pair<string, int>> v;
//진수 구하기
string s = "";
while(n > 0) {
s += to_string(n % k);
n /= k;
}
reverse(s.begin(), s.end());
//211020101011
string tmp = "";
for (char c : s) {
if (c == '0') {
if (!tmp.empty() && isPrime(stoll(tmp))) {
answer++;
}
tmp = "";
}
else tmp += c;
}
if (!tmp.empty() && isPrime(stoll(tmp))) { //마지막꺼
answer++;
}
return answer;
}*0을 기준으로 나누었기 때문에, 맨끝에 숫자는 카운트 되지 않는다. 그렇기 때문에 반복문을 나오고 나서 한번 더 확인하고 카운트+1를 해주어야 한다.
🐥주의할 점
-> 진수 변환 시 숫자의 길이가 길어져 long long 타입을 사용해주어야 한다.
기록하기