[Lv2]소수찾기(C++)

1. 문제

programmers.co.kr/learn/courses/30/lessons/42839?language=cpp

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

2. 접근 방법

1) numbers의 각 자리 숫자를 char 단위로 입력 받음 => vector<char> v;

 

2) 만들 수 있는 숫자의 길이는 최소 한 자리수부터 최대 v.size()자리 수 이므로, 각 자리수 만큼 순열을 구함

(ex. 1개 순열, 2개 순열 ,.... v.size() 개 순열 을 구함)

 

3) 각 순열에 의해 만들어졌던 수에 소수판별 진행

 

 

3. 실수했던 부분 & 처음 알았던 부분

1) 반복해서 소수가 카운팅 되는 경우

  - 1,1,0을 뽑으면 순열에 의해 11이 두 번 들어갈 수 있다. 따라서 이미 소수 판별을 한 수는 set에 저장함으로써 중복 카운팅을 막았다.

 

2) 0으로 시작하는 수

 - -if문으로 가장 첫 번호가 0일 경우 건너가도록 했다.

 

4. 코드

#include<iostream>
#include<string>
#include<cmath>
#include<set>
#include<algorithm>
#include<vector>
using namespace std;
int cnt;
vector<char> ch; //순열 벡터
vector<char> v; //원본 벡터
bool visited[8];
set<int> s; //이미 계산했던 값인지 판단 

void isSoSu(int num) { // num이 소수인지
    if( num <= 1 ) return;
    for(int i = 2;i<=(int)sqrt(num);i++) 
        if(num % i == 0) return;
    cnt++;
}

void go(int cur ,int num ) {
    if( cur > num) return;
    else if(cur == num ) {
        //지금까지의 조합이 소수인지 판단
        int number=0;
        for(auto x : ch) 
            number = number*10 + (int)(x-'0');
         if( s.find(number) != s.end()) return; //이미 소수판단 한 값이면 계산 넘어가기
        s.insert(number);
        isSoSu(number);
    }
    
    for(int i=0;i<v.size();i++) {
        if(visited[i]) continue;
        if(i == 0 && v[i] == 0) continue;
        visited[i] = true;
        ch.push_back(v[i]);
        go(cur+1,num);
        ch.pop_back();
        visited[i] = false;
    }
}

int solution(string numbers) {
    int siz = numbers.size();
    
    for(int i=0;i<siz;i++)
        v.push_back(numbers[i]);
    
    //모든 수 구하기. 수는 최소 1자리수 부터 최대 max자리수 까지 만들 수 있음
    for(int k =1; k<=siz;k++) {
        fill(&visited[0],&visited[8],false);
        go(0,k);
    }
    return cnt;   
}