[프로그래머스] 소수 찾기 (C++)

[아이디어]

그냥 구현 하는 식으로 풀었습니다.

 

 

[요약]

카드를 조합해 나올 수 있는 소수 찾기

 

 

[방법]

문자열에서 각 자리를 분리해

0~9까지 정수를 추출 합니다.

 

카드 조합 중 나올 수 있는 가장 큰 수를 찾습니다.

 

1부터 방금 구한 가장 큰 수까지

소수를 판별합니다.

 

카드를 조합해

조합한 수가 소수인지 아닌지 판별해줍니다.

 

 

[설명]

dfs(모든 카드의 장수, 재귀 단계, 카드 조합을 통해 구한 수)

백트래킹을 사용해 모든 카드 조합을 찾음

 

vector에서 중복 값을 제거

//-----------------------------------------------------
// 중복 제거 처리
    
// 중복을 제거하기 위한 정렬을 한다.
sort(ans.begin(), ans.end());
// unique()는 중복된 값을 vector의 가장 뒤로 보내고
// 이러한 값을 보낸 시작 위치를 반환한다.
// erase()를 사용해 중복값이 존재하는 위치부터 끝까지 지워준다.
ans.erase(unique(ans.begin(), ans.end()),ans.end());
//-----------------------------------------------------

중복을 제거하기 위해 unique()를 사용합니다.

다만,

정렬되지 않은 vector에 대해 unique를 적용한다면 아무런 변화가 없습니다.

그렇기에

unique()를 적용하기 전에 vector를 먼저 정렬해주고

unique()를 적용하면 중복값이 제거되.....

.....

.....

지 않습니다.

그 이유는 중복값을 vector의 끝 부분에 보냈을 뿐

vector 끝 부분에 존재하기 때문입니다.

또한 unique()는 중복값을 보낸 시작위치를 가르킵니다.

 

그래서,

erase()함수를 통해 unique()가 가르킨 위치부터

마지막까지 지워주면

깔끔하게 중복값은 제거됩니다.

 

 

[코드]

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

using namespace std;

#define N_MAX 10000000
#define FOR(i,s,e) for(int i=s; i<e; ++i)

vector<int> v;
bool arr[N_MAX];
int num;
vector<int> ans;
vector<int> used;

void dfs(int max_lv, int lv, int n) {
    if (max_lv == lv) {
        if (arr[n] == true)  ans.push_back(n);
        return;
    }
    FOR(i, 0, v.size()) {
        if (used[i] == 1) continue;
        used[i] = 1;
        n = (n * 10) + v[i];
        dfs(max_lv, lv + 1, n);
        n = (n / 10);
        used[i] = 0;
    }
}

int solution(string numbers) {
    int answer = 0;

    //-----------------------------------------------------
    //문자열에서 각 숫자 카드를 '한장 씩' 추출
    FOR(i, 0, numbers.length()) {
        v.push_back(int(numbers[i] - '0'));
    }
    //-----------------------------------------------------


    //-----------------------------------------------------
    //가장 큰 수를 확인하기 위해 내림차순으로 정렬
    sort(v.begin(), v.end(), greater<int>());

    // num변수에 가장 큰 수 저장
    FOR(i, 0, v.size()) {
        num = (num * 10) + v[i];
    }
    //-----------------------------------------------------

    
    //-----------------------------------------------------
    // 소수확인 후 판별하기 위한 arr배열 초기화
    // 소수라면 true, 아니라면 false
    memset(arr, true, sizeof(arr));
    
    // 0과 1은 소수가 아니다.
    arr[0] = false;
    arr[1] = false;

    // 가장 큰 수 9999999이므로 배열의 크기는 10000000
    // 카드 조합 중 나올 수 있는 가장 큰 수(num)까지 소수 판별을 한다.
    FOR(i, 1, 10000000) {
        if (arr[i] == false) continue;
        int s = i;
        for (int j = i * 2; j <= num; j += i) {
            arr[j] = false;
        }
    }
    //-----------------------------------------------------

    //-----------------------------------------------------
    // 카드를 조합해 나올 수 있는 모든 수를 구한다.
    FOR(i, 1, v.size() + 1) {
        used = vector<int>(v.size(), 0);
        dfs(i, 0, 0);
    }
    //-----------------------------------------------------

    
    //-----------------------------------------------------
    // 중복 제거 처리
    
    // 중복을 제거하기 위한 정렬을 한다.
    sort(ans.begin(), ans.end());
    // unique()는 중복된 값을 vector의 가장 뒤로 보내고
    // 이러한 값을 보낸 시작 위치를 반환한다.
    // erase()를 사용해 중복값이 존재하는 위치부터 끝까지 지워준다.
    ans.erase(unique(ans.begin(), ans.end()),ans.end());
    //-----------------------------------------------------

    answer = ans.size();
    return answer;
}

 

[문제 출처]

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

프로그래머스