프로그래머스 소수 찾기 c++

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

 

제한사항

numbers는 길이 1 이상 7 이하인 문자열입니다. numbers는 0~9까지 숫자만으로 이루어져 있습니다. 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

 

입출력 예

17	3
011	2

 

 

입출력 설명

 

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

 

=> 소수를 찾을 줄 아는지 묻고, 주어진 카드로 만들 수 있는 모든 경우의 수를 확인하는 문제입니다. 

 

 

• 에라토스테네스의 체를 이용해 numbers의 가장 큰 숫자의 경우까지 실행합니다. 
• numbers를 sort한 후에, permutation을 사용해 지속적으로 만들 수 있는 숫자를 확인합니다. 
• substr를 통해 단일 숫자나 그 중 조금의 숫자가 뽑히는 경우를 생성합니다. 
• set을 사용하여 중복을 제거합니다. 

 

<code>

int solution(string numbers) {
    string s= numbers;
    sort(s.begin(), s.end(),greater<char>());
    int max = stoi(s);
    bool *check = new bool[max+1];
    
    fill_n(check, max+1, false);
    
    check[1]=true;
    check[0]=true;
    int answer = 0;

    for(int i=2; i<max+1; i++)
    {
        if(check[i] == false)
        {
            for(long j= i*i; j<max+1; j+=i)
            {
                check[j] = true;
            }
        }
    }
    
    sort(numbers.begin(), numbers.end()), greater<char>();
    set<int> ans;
    
    do{
        for(int i=1; i<=numbers.size(); i++) {
            string tmp = numbers.substr(0, i);
            if(check[stoi(tmp)] == false) {
                ans.insert(stoi(tmp));
            }
        }
    } while(next_permutation(numbers.begin(), numbers.end()));
    
    return ans.size();
}

 

 

 

xcode 실행 화면

 

 

---

프로그래머스에서 문제풀이를 하는 방식은 생각보다 힘듭니다. 리눅스에서 코딩하는 느낌....
IDE를 쓰고 싶지만, 코딩테스트를 대비해서 연습하고 있습니다. 

가뜩이나 작은 화면을 문제내용으로 가로막고 있으니 시인성이 더 안 좋습니다...ㅠㅠ

그래도 익숙해지도록 노력해야 하겠습니다.