프로그래머스 소수 찾기 문제

안녕하세요! 오늘은  프로그래머스 소수찾기 문제를  풀었습니다.

programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기

 

이 문제는 모든 경우의수를 따지기만해도 충분히 풀 수 있습니다.

 

numbers 길이가 최대 7이고, numbers는 숫자 0~9로 이루어져있기에

최대 가능한 숫자가 9,999,999 입니다.  

에라토스테네스의 체를 이용해  소수를 파악하고,

numbers 길이가 최대 7이므로  나올 수 있는 모든 숫자 경우의 수가 7! 입니다.

 

이런 상황이기에   완전탐색으로해도  시간내 풀이가 가능한것이죠.

 

#include <string>
#include <vector>
using namespace std;


 //값 0인애들이 소수 (2이상일떄) 
int isPrime[10000000]={};
int canCnt = 0;
int visited[8]={};

//모든 경우의수 따지기
void findCase(int step, int num, string numbers){
	if(step == numbers.size()){
		if(isPrime[num] == 0) {
			canCnt++;
			isPrime[num] = 2;
		}
		return ;
	}
	
	for(int i=0;i<numbers.size();i++){
		if(visited[i] == 0){
			visited[i] = 1;
            //해당 숫자를 포함하거나
			findCase(step+1, num*10 + (numbers.at(i)-'0'), numbers);
            //숫자 건너띄거나
            findCase(step+1, num, numbers);
			visited[i] = 0;
		}
	}
}

int solution(string numbers) {
    int answer = 0;
    isPrime[1]=2;
    
    //소수 여부 담기  (값이 0인애가 소수)
    for(int i=2; i*i<=9999999;i++){
    	if(isPrime[i] == 2) continue;
    	
    	if(isPrime[i] == 0){
    		for(int j=2;j*i<=9999999;j++){
    			isPrime[i*j] = 2;
    		}
    	}
    }
    

//백트랙하면서 가능한 모든숫자 표시
	for(int i=0;i<numbers.size();i++){
		visited[i]=1;
        if(numbers.at(i) != '0')
            findCase(1, numbers.at(i)-'0', numbers);
		visited[i]=0;
	}
	
	 
	answer=  canCnt;
    
    
    
    return answer;
}

 

 

<박기완의 c언어 코딩교육 시리즈 >

게임개발을 희망하는 초등학생, 중학생, 고등학생들을 위한 c언어 책

 

초등, 중등, 고등  1:1 원격 c언어 교육문의

010 - 4537 - 7998

 

현재 대치동 학원에서 코딩강사로 활동중에 있습니다

영재고, 과학고 내신 /

초등, 중등, 고등 입문반, 초급, 중급, 정올반 /

앱, 게임 제작반  문의주세요!