Gidhub BE Developer

[BOJ] 3671. 산업 스파이의 편지

2018-09-26
goodGid
Algorithm

Problem

Problem URL : 산업 스파이의 편지

[1] Answer Code (18. 09. 26)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;

bool p[10000000]; // p is Prime Number
bool c[10000000];

int solution(string s) {
    int ans=0;
    int size = (int)s.size();
    sort(s.begin(),s.end());
    do{
        for(int i=1; i<=size; i++){
            int n;
            n = stoi(s.substr(0,i));
            if(!c[n] && p[n]){
                c[n] = true; // n값은 사용했다.
                ans++;
            }
        }
    } while(next_permutation(s.begin(),s.end()));
    return ans;
}

int main(){
    memset(p,1,sizeof(p));
    p[0] = false;
    p[1] = false;
    for(int i=2; i*i<10000000; i++){
        if(p[i] == false) continue; // p[i] is not Prime Number
        p[i] = true;
        for(int j=i*2; j<10000000; j+=i)
            p[j] = false;
    }
    
    int t;
    string _s;
    cin >> t;
    while(t--) {
        memset(c,0,sizeof(c));
        cin >> _s;
        cout<<solution(_s)<<'\n';
    }
    return 0;
}

Review

  • 처음에 main함수에서 일정범위까지 소수를 미리 구해놓는다.

  • 그 후 solution 함수에서 작업을 진행한다.

1234일 때

1
12
123
1234 를 체크하고

next_permutation()함수로 
1234 -> 1243으로 바뀐다.
그렇게 되면
1
12
124
1243 를 체크한다.

이렇게 반복시키면 최종적으로는 모든 경우의 수를 다 살핀다.

[2] Answer Code (18. 09. 26)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;

bool p[10000000]; // p is Prime Number

int solution(string s) {
    set<int> se;
    int ans=0;
    int size = (int)s.size();
    sort(s.begin(),s.end());
    set<int>::iterator iter;
    
    do{
        for(int i=1; i<=size; i++){
            int n;
            n = stoi(s.substr(0,i));
            iter = se.find(n);
            if(iter == se.end() && p[n]){
                se.insert(n);
                ans++;
            }
        }
    } while(next_permutation(s.begin(),s.end()));
    return ans;
}

int main(){
    memset(p,1,sizeof(p));
    p[0] = false;
    p[1] = false;
    for(int i=2; i*i<10000000; i++){
        if(p[i] == false) continue; // p[i] is not Prime Number
        p[i] = true;
        for(int j=i*2; j<10000000; j+=i)
            p[j] = false;
    }
    
    int t;
    string _s;
    cin >> t;
    while(t--) {
        memset(c,0,sizeof(c));
        cin >> _s;
        cout<<solution(_s)<<'\n';
    }
    return 0;
}

Review

  • [STL] set을 사용한 풀이

Recommend

Index