소수판별법, K진수 바꾸는법만 알면 간단했던문제,
사실 간단하진 않고, 실제 시험장이라고 가정하면 일단 완벽히 못맞추고 1번과 11번을 100퍼센트 틀렸다.
아마 부분점수가 없다면, 1번에서 나가리...
이문제는 딱 두가지만 알면된다.
1. 소수판별법
2. k진수 바꾸는법
소수판별법
bool isPrime(long long n) {
if(n==1) return false;
for (int i = 2; i <= sqrt(n); i++) {//2~n의 제곱근까지
if (n%i == 0) {//i가 n의 약수라면 소수가 아니므로 false return
return false;
}
}
//2 ~ n-1까지 약수가 없다면 소수이므로, true return
return true;
}소수판별법에서 일단 n이 1이면 무조건 false를 return하고
그게 아니면 2부터 ~n의 제곱근까지 약수인지 아닌지 판별하면 된다. 너무 유명한 코드라 다른 설명은 안하겠다.
다만 중요한점은 여기 isPrime의 파라미터를 반드시 longlong으로 해야하는것인데, 제한조건 판별은 아주 기본적인 건데 내가 실수로 생각을 미처 하지 못했다.
왜냐하면, 제한조건인 n이 1,000,000이므로 백만을 이진수로 바꾸면,
1111 0100 0010 0100 0000 인데 이게 int의 범위를 무조건 넘어간다. 그러므로 long long으로 선언하는것이 중요하다.
K진수로 바꾸기
이것도 어느정도 널리 알려져있는 방법인데,
string number = "0123456789ABCDEF"; //16진수 까지의 가능한 각 자리 수
string change(int num, int binary) { //num = n, binary = k
string result; //변환 결과
if (num == 0) {
return "0"; //num이 0일경우 0반환
}
while (num > 0) {
result = number[num % binary] + result; //16진수까지의 변환 number이용하여 reverse 사용하지 않음.
num /= binary; //진수 계산.
}
return result;
}num이 0이면 일단 0을 return하고 그게아니면 while문을 도는데
binary를 %로 나누고 그 값인 result로 더하면 된다.
그다음 몫을 계산하기 위해 num/=binary로 하면된다.
solution
int solution(int n, int k) {
string s = change(n,k);
string check="";
for(long long i=0;i<s.size();i++){
if(s[i]!='0'){
check+=s[i];
}else if(check.size()>0){
if(isPrime(stol(check))){
answer++;
check="";
}
check="";
}
}
if(check.size()>0 && isPrime(stol(check))) {
answer++;
}
return answer;
}일단 change함수를 통해서 각 K진수로 바꾸고, 0이아니면 check에다가 이어붙이고 0이면 검사를 한다.
여기서 포인트는
- 11000인경우 11을 검사하고 난뒤에 0부터는 계속 else if 문으로 들어가므로 check의 size가 0보다 큰지 확인한다.
- 여기서 내가 틀렸었는데 stoi가 아니라 stol이다... 왜냐? 앞에서 말했듯이 check가 100만의 이진수면 stol이면 int보다 큰 long long type일 수도 있기 때문이다.
- 마지막으로 110011 인경우 11로 끝나면 check에 11이 남아있으므로, check.size()가 0보다 크면 검사를 한다.
전체코드
#include <string>
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int answer=0;
string number = "0123456789ABCDEF"; //16진수 까지의 가능한 각 자리 수
string change(int num, int binary) { //num = n, binary = k
string result; //변환 결과
if (num == 0) {
return "0"; //num이 0일경우 0반환
}
while (num > 0) {
result = number[num % binary] + result; //16진수까지의 변환 number이용하여 reverse 사용하지 않음.
num /= binary; //진수 계산.
}
return result;
}
bool isPrime(long long n) {
if(n==1) return false;
for (int i = 2; i <= sqrt(n); i++) {//2~n의 제곱근까지
if (n%i == 0) {//i가 n의 약수라면 소수가 아니므로 false return
return false;
}
}
//2 ~ n-1까지 약수가 없다면 소수이므로, true return
return true;
}
int solution(int n, int k) {
string s = change(n,k);
string check="";
for(long long i=0;i<s.size();i++){
if(s[i]!='0'){
check+=s[i];
}else if(check.size()>0){
if(isPrime(stol(check))){
answer++;
check="";
}
check="";
}
}
if(check.size()>0 && isPrime(stol(check))) {
answer++;
}
return answer;
}여기서 내가 틀린부분은 두가지이다.
우선 isPrime을 할때 int가 아닌 long long으로 선언해야하는것 => why? 100만을 이진수로 바꾸면 int범위를 넘어서기 때문
두번째로는, stoi가 아니라 stol로 해야하는것.
아쉽다.
