[C++] 프로그래머스 소수찾기 완전탐색

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(string numbers) {
    int answer = 0;
    
    sort(numbers.rbegin(), numbers.rend());
    int num = stoi(numbers);
    
    vector<bool> visited(num + 1, false);
    
    for(int i = 2; i <= num; i++)	//소수를 찾는다.
    {
        if(!visited[i])
        {
            for(int j = i + i; j <= num; j += i)	//찾으면 그것의 배수들은 소수가 아니므로 다 표시
            {
                visited[j] = true;
            }
        }
    }
    
    for(int i = 2; i <= num; i++)
    {
        if(!visited[i])
        {
            string temp = to_string(i);	//갈 소수를 string으로 변환
            int counts = 0;
            vector<bool> numVisited(numbers.size());	//현재 numbers에서 방문한 곳이 있으면 표시
            
            for(int j = 0; j < temp.size(); j++)	//현재 소수에 필요한 자리만큼 반복
            {
                for(int k = 0; k < numbers.size(); k++)	//한 소수당 모든 numbers를 방문
                {
                    if(temp[j] == numbers[k] && !numVisited[k])	//수가 같고 방문 안 했을때만.
                    {
                        numVisited[k] = true;
                        counts++;
                        break;	//수가 같은 수가 있을 수 있으므로 
				//무조건 break로 나가서 다음자리수를 계산한다.
                    }
                }    
            }
            
            if(counts == temp.size())	//같은 수가 있는 개수가 소수의 자릿수와 같을 때
					//소수의 개수 하나추가
            {
                answer++;
            }
        }
    }//for(int i = 2; i <= num; i++)
    
    
    return answer;
}

 

풀이

1. 최대 범위는 numbers를 최대 큰 숫자들로 정렬한 것과 같기 때문에 내림차순 정렬을 한다.
2. 그 수를 int로 형변환한다.
3. 소수가 아닌 것들을 판단하기 위해서 처음 나온 수가 있으면 그것의 배수들을 모두 체크해준다.
4. 해당 소수들이 numbers안에 숫자가 들어 있나 한 자리씩 체크해준다.