[프로그래머스 C++] 타겟 넘버

 

[프로그래머스 C++] 타겟 넘버

 

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

프로그래머스

---

 

해결전략

 

소수 구하기, 에라토스테네스의 체 (맨 아래에 코드 설명 참조)

문자열

stol

 

주의할 점!

• 진법 변화 시 검사하는 숫자값이 커지니 int가 아닌 long long을 사용해야 한다.  stoi (x),  stol (o)  
• 소수 판정 방법

---

 

처음 시도한 코드

 

#include <string>
#include <vector>
using namespace std;
 
int solution(int n, int k) {
    int answer = 0;
 
	string cNum = "";
    while(n>0)
    {
        string temp = to_string(n % k);
        cNum = temp + cNum;
 
        n /= k;
    }
    
    string tmp = "";
    long long tmpNum = -1;
    for(int i=0; i<cNum.size()+1; i++)
    {
        if (cNum[i] == '0' || cNum[i] == '\0')
        {
            // 소수 확인
            if (tmp != "") {
                tmpNum = stol(tmp);
            }
 
            if(tmpNum > 1)
            {
                for (int j = 2; j < tmpNum; j++) {
                    if (tmpNum % j == 0) {
                        break;
                    }
                }                
                answer++; //위에서 break 안 걸렸다면 소수
            }           
 
        	tmp = "";
            tmpNum = -1;
        }
        else
        {
            tmp = tmp + cNum[i];
        }        
    }
 
    return answer;
}

 

 

테스트 케이스 11, 12, 14, 15, 16 실패

---

 

정답 코드

 

#include <string>
#include <vector>
using namespace std;
 
bool isPrime(long long x) // 주어진 숫자 x가 소수인지 확인하는 함수
{
    if (x <= 1) // 1 이하의 수는 소수가 아님
        return false;
 
    if (x == 2 || x == 3) // 2와 3은 소수
        return true;
 
    if (x % 2 == 0 || x % 3 == 0) // 짝수나, 또는 합성수(6의 배수)이면 소수가 아님
        return false;
 
    for (long long i = 5; i * i <= x; ++i)
    {
        // i나 i+2로 나누어 떨어지면 합성수로 판단.
        if (x % i == 0 || x % (i + 2) == 0)
            return false;
    }
 
    return true; // 위 조건을 모두 만족하지 않으면 소수로 판단.
}
 
int solution(int n, int k) {
    int answer = 0; // 결과값을 저장할 변수
 
	//** 주어진 수 n을 k진법으로 변환하는 과정
	string cNum = "";
    while(n>0)
    {
        string temp = to_string(n % k);
        cNum = temp + cNum;
        n /= k;
    }
 
	//** 변환된 k진법 문자열에서 '0' 또는 문자열의 끝('\0')을 기준으로 분리된 부분들이 소수인지 검사하는 과정	
	string tmp = "";
	long long tmpNum = -1;
	for(int i=0; i<cNum.size()+1; i++)//문자열의 끝('\0') 검사를 위해 cNum.size()+1
	{
	    if (cNum[i] == '0' || cNum[i] == '\0')
	    {            
	        if (tmp != "") {
	            tmpNum = stol(tmp); //문자열 long long으로 변환 
	        }
			// 분리된 부분이 소수라면 answer 값을 증가시킴.
	        if(isPrime(tmpNum) == true){      
	            answer++;
	        }           
	
	    	tmp = ""; 	 // tmp 초기화
	        tmpNum = -1; // tmpNum 초기화
	    }
	    else
	    {
			tmp += cNum[i];
	    }        
	}
 
	return answer;
}

 

---

 

 

 

소수 구하기 방법들

 

bool isPrime(long long x) // 주어진 숫자 x가 소수인지 확인하는 함수
{
    if (x <= 1) // 1 이하의 수는 소수가 아님
        return false;
 
    if (x == 2 || x == 3) // 2와 3은 소수
        return true;
 
    if (x % 2 == 0 || x % 3 == 0) // 짝수나, 또는 합성수(6의 배수)이면 소수가 아님
        return false;
 
    for (long long i = 5; i * i <= x; ++i)
    {
        // i나 i+2로 나누어 떨어지면 합성수로 판단.
        if (x % i == 0 || x % (i + 2) == 0)
            return false;
    }
 
    return true; // 위 조건을 모두 만족하지 않으면 소수로 판단.
}

 

 

 

에라토스테네스의 체

#include <vector>
using namespace std;
 
bool eratosthenes(int n) {
    if (n <= 1) {
        return false; // 1 이하의 수는 소수가 아니다.
    }
 
    vector<bool> prime(n + 1, true); // 처음에는 모든 수가 소수라고 가정
 
    prime[0] = prime[1] = false; // 0과 1은 소수가 아니다.
 
    for (int i = 2; i * i <= n; ++i) 
    {
        if (prime[i]) // 만약 해당 수가 아직 지워지지 않았으면
        { 
            for (int j = i * i; j <= n; j += i) { // 그 배수들을 모두 지움
                prime[j] = false;
            }
        }
    }
 
    return prime[n]; // 입력받은 값 n이 최종적으로 남아있다면 그것은 소수임
}

 

 

 

에라토스테네스의 체는 특정 범위 내에서 소수를 찾는 방법이다. 

1. 2부터 시작하여 숫자를 배열에 저장합니다.
2. 2부터 시작하여 해당 숫자의 배수를 모두 제거합니다.
3. 다음으로 남아 있는 가장 작은 수(이미 제거되지 않은 수)를 찾고 그 배수를 모두 제거합니다.
4. 위 과정을 반복하여 더 이상 배수를 제거할 수 없을 때까지 진행하면, 배열에 남아 있는 수들이 소수입니다.
   
   

#include <iostream>
#include <vector>
using namespace std;
 
void eratosthenes(int n) {
    vector<bool> prime(n + 1, true); // 처음에는 모든 수가 소수라고 가정
 
    prime[0] = prime[1] = false; // 0과 1은 소수가 아님
 
    for (int i = 2; i * i <= n; ++i) 
    {
        if (prime[i]) // 만약 해당 수가 아직 지워지지 않았으면
        { 
            for (int j = i * i; j <= n; j += i) { // 그 배수들을 모두 지움
                prime[j] = false;
            }
        }
    }
 
    // 출력 부분: 남아있는 소수들 출력
    for (int i = 2; i <= n; ++i) {
        if (prime[i]) {
            cout << i << ' ';
        }
    }
}
 
int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;
 
    eratosthenes(n);
 
   return 0;
}

 

---