[programmers] 완전탐색, 소수찾기

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

코딩테스트 연습 - 소수 찾기 | 프로그래머스

 

문제

0~9로 이루어진 종이 조각이 주어지면, 종이 조각으로 만들 수 있는 소수가 몇 개인지 반환하는 문제입니다. 종이조각의 개수는 1~7 입니다.

해결

1. 주어진 종이조각들로 만들 수 있는 숫자 조합을 배열에 모두 저장해둔다.
2. 배열에 저장되어있는 숫자들 중 똑같은 수가 여러개일 수 있으므로 중복을 제거해준다.
3. 배열을 순환하여 원소가 소수이면 cnt 를 1씩 증가시킨다.
4. cnt 를 반환한다.

배열 중복을 제거하는 법

vector<int> v 를 유일한 원소들의 집합으로 만들고 싶다면, 

1. 정렬을 한다. : sort
2. 연속된 중복 원소를 vector의 제일 뒷부분(쓰레기 값)으로 보내버린다. : unique
3. 중복된 원소들이 모여있는 뒷부분을 삭제한다 : erase

unique 함수는 반환값이 vector 쓰레기 값의 첫번째 위치가 되므로 바로 erase 함수 안에 중첩해서 사용할 수 있습니다.

sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

 

코드

#include <cstdio>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <algorithm>
#define MAX 10000005
using namespace std;
int prime[MAX], chk[MAX];
vector<int> v;
 
void prime_chk() {
    for (int i = 2; i <= sqrt(MAX); i++) {
        if (!prime[i]) {
            for (int j = i * 2; j <= MAX; j += i) {
                prime[j] = 1;
            }
        }
    }
}
 
void make_num(string numbers, string now, int len, int idx) {
    if (now.size() > 0) {
        v.push_back(stoi(now));
    }
    if (len == idx) return;
    
    for (int i = 0; i < numbers.size(); i++) {
        if (chk[i]) continue;
        chk[i] = 1;
        now.push_back(numbers[i]);
        make_num(numbers, now, len, idx+1);
        now.pop_back();
        chk[i] = 0;
    }
    return;
}
 
int solution(string numbers) {
    int cnt = 0;
    prime_chk();
    prime[0] = prime[1] = 1;
 
    // 숫자 만들기
    string tmp;
    make_num(numbers, tmp, numbers.size(), 0);
 
    // 중복제거
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
 
    // 소수판별
    for (int i = 0; i < v.size(); i++) {
        if (!prime[(v[i])]) cnt++;
    }
    return cnt;
}
 
using namespace std;
int main() {
    string numbers;
    cin >> numbers;
    
    printf("%d", solution(numbers));
    
    return 0;
}