99클럽 코테 스터디 6일차 TIL : 완전탐색 - 소수찾기

어마어마한 삽질과 함께,,,,,,

3시간이 걸렸다..ㅋㅋㅋㅋㅋㅋ아짜증나!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

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

---

문제는 간단했다.

숫자가 string으로 주어지면, 해당 string을 조합해서 만들 수 있는 모든 경우의 수 중 소수가 몇개인지를 찾는 문제였다.

 

1. string으로 주어진 숫자를 조합해 가능한 모든 순열을 찾는다

2. 찾은 순열 중 소수의 개수를 찾는다.

 

나는 여기서 순열찾기가 좀,,,, 에바였다.

 

permutation 기본 알고리즘은 이렇다

1. n개의 숫자들이 vector로 주어진다 (size : n)

2. n이 1인 경우 == 순열은 주어진 숫자 그대로 -> 그대로 리턴한다

3. 아닌경우, 반복과 재귀를 통해 순열을 찾는다.

    주어진 vector중 하나를 prefix로 고정한다.

    나머지 숫자들 (n-1 size의 vector)을 input으로 permutation을 구한다. -> other

    other와, 길이가 n-1인 other에 prefix를 붙인다. -> 이게 result

 

처음 문제가 됐던건 vector<int>를 사용했다는 점이다.

아직 붙일 prefix가 남은 상황에는, 지금 순열의 맨 앞에 0이와도 된다! (1 + 023 = 1023이 될 수 있음)

즉 vector<string>으로 진행을 해야했다.

 

두번째는 other에 대한 제한이 없었다는 점이다.

재귀 특성상, size n에서 받은 other은 size n-1 ~ 1까지 모든 경우의 수가 담겨서 온다.

하지만 prefix가 붙어야 하는건 size가 n-1인 경우에만 붙이고, 나머지 other에 대해서는 추가적인 동작이 필요하지 않는다.

이부분에서 문제가 되어 2시간동안 삽질에삽질에삽질을,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

 

[문제가 됐던 코드 -> 틀린코드이다]

#include <string>
#include <vector>
#include <iostream>
#include <cmath>
#include <sstream>
#include <algorithm>

using namespace std;


bool isprime(int n){
    if(n<2){
        return false;
    }
    if(n == 2){
        return true;
    }
    for(int i = 2; i <= sqrt(n); i++){
        if((n % i) == 0){
            return false;
        }
    }
    
    return true;
}


vector<int> permutation(vector<int> numbers){
    // numbers로 만들 수 있는 조합들 
    vector<int> result;
    if(numbers.size() <= 1){
        result = numbers;
        return result;
    }
    
    int numsi = numbers.size();
    for(int i = 0; i < numsi; i++){
        int prefix = numbers[i];
        vector<int> next = numbers;
        next.erase(next.begin() + i);
        vector<int> other = permutation(next);
        
        int othersize = other.size();
        
        for(int j = 0; j < othersize; j++){
            
            result.push_back(other[j]);
            result.push_back((prefix * (int)pow(10,numsi-1)) + other[j]);
        }
    }
    
    sort(result.begin(), result.end());
    result.erase(unique(result.begin(),result.end()),result.end()); // 중복제거
    return result;
}

int solution(string numbers) {
    int answer = 0;
    
    vector<int> numbersvec;
    vector<int> primes;
    
    for(int i = 0; i<numbers.size(); i++){
        numbersvec.push_back(numbers[i] - '0');
    }
    
    
    sort(numbersvec.begin(), numbersvec.end());
    
    
    int num = numbers.size();

    vector<int> test = permutation(numbersvec);
    
    sort(test.begin(), test.end());
    test.erase(unique(test.begin(),test.end()),test.end());
    
    for(int i =0; i<test.size(); i++){
        if(isprime(test[i])){
            answer++;
        }
        
    }
    
    
    
    return answer;
}

 

[해결한 코드]

#include <string>
#include <vector>
#include <iostream>
#include <cmath>
#include <sstream>
#include <algorithm>

using namespace std;


bool isprime(int n){
    if(n<2){
        return false;
    }
    if(n == 2){
        return true;
    }
    for(int i = 2; i <= sqrt(n); i++){
        if((n % i) == 0){
            return false;
        }
    }
    
    return true;
}


vector<string> permutation(vector<string> numbers){
    // numbers로 만들 수 있는 조합들 
    vector<string> result;
    if(numbers.size() <= 1){
        result = numbers;
        return result;
    }
    
    int numsi = numbers.size();
    for(int i = 0; i < numsi; i++){
        
        string prefix = numbers[i];
        //cout << "numbers.size() : "<<numsi<<", prefix : " <<prefix<<endl;
        vector<string> next = numbers;
        next.erase(next.begin() + i);
        vector<string> other = permutation(next);
        
        int othersize = other.size();
        
        for(int j = 0; j < othersize; j++){
            
            result.push_back(other[j]);
            if(other[j].size() > (numsi-2)){
                
                string text = prefix + other[j];
                //cout << "in per, text : " << text << endl;
                result.push_back(text);
            }
        }
    }
    
    //sort(result.begin(), result.end());
    //result.erase(unique(result.begin(),result.end()),result.end()); // 중복제거
    return result;
}

int solution(string numbers) {
    int answer = 0;
    
    
    
    vector<int> numbersvec;
    vector<string> numberst;
    vector<int> primes;
    
    
    
    for(int i = 0; i<numbers.size(); i++){
        numbersvec.push_back(numbers[i] - '0');
        std::string s{numbers[i]};
        numberst.push_back(s);
    }
   
    
    
    sort(numbersvec.begin(), numbersvec.end());
    
    
    int num = numbers.size();

    vector<string> test = permutation(numberst);
    
    vector<int> mypers;
    
    for(int i = 0; i<test.size(); i++){
        //cout << test[i] << endl;
        mypers.push_back(stoi(test[i]));
    }
    
    sort(mypers.begin(), mypers.end());
    mypers.erase(unique(mypers.begin(),mypers.end()),mypers.end());
    
    for(int i =0; i<mypers.size(); i++){
        if(isprime(mypers[i])){
            primes.push_back(mypers[i]);
        }
        
    }
    
    
    answer = primes.size();
    
    return answer;
}

---

소수구하기 자체를 너무 오랜만에봤고

순열, 조합구하는 방법을 전부 까먹었다,,,ㅋㅎ,,,,

 

c++에 permuatation관련해서 사용할 수 있는 함수가 있는것같긴한데

정확한 사용법을 이해하진 못했고, 내 구현에서는 굳이 필요가 없어보여서 사용하지 않았다.

 

에휴,,,