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

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

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

입출력 예numbersreturn

"17"	3
"011"	2

입출력 예 설명

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

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

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

---

이문제 레벨 2 아닌거같다

개인적으로 너무 어려웠음..

 

나는 2부터 문자열 numbers로 만들 수 있는 가장 큰 수 범위에 있는 소수를 구한다음,

그 소수가 numbers 원소를 포함하고 있는지 체크해서 풀었음.

 

우선 numbers를 정렬한 후에 새로운 string max에 거꾸로 넣어서 가장 큰 수를 만들어줌

i가 2부터 max 범위에 있는 소수일때만(소수판별은 isPrime 함수 이용)

i를 string으로 변환해서 numbers와 비교해줌.

만약 같은 숫자를 찾으면 카운트해주고 numbers원소 삭제해줌

(numbers는 다시 사용해야하므로 임시로 tmp 사용)

 

처음엔 그냥 i에서 numbers[j]를 find해서 카운트했는데

중복되는 원소가 있을경우 정상적으로 출력되지 않았음..(numbers [1,1,0]인데 13들어올경우 카운트 2됨)

그래서 numbers에서 중복되는 원소를 다 삭제했더니 이번엔 11이 들어온경우 체크가 안됨..

결국 자리수대로 비교하는 방법으로 변경,,3중 포문이 되버림

 

더 간단하게 비교하는 방법이 있을거같은데 지금은 머리가 안돌아서 모르겠다..

#include <string>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

bool isPrime(int n) {
    if (n < 2) return false;

    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0) return false;

    return true;
}

int solution(string numbers) {
    int answer = 0;
    int cnt = 0;
    string max = "";

    sort(numbers.begin(), numbers.end());
    
    for(int i = numbers.size()-1; i >= 0; i--)
    {
        max += numbers[i];
    }
    
    int max_num = stoi(max);
  
    for(int i = 2; i <= max_num; i++)
    {
        if(isPrime(i))
        {
            cnt = 0;
            string stri = to_string(i);
            string tmp = numbers;
            
            for(int a = 0; a < stri.size(); a++)
            {
                for(int b = 0; b < tmp.size(); b++)
                {
                    if(stri[a] == tmp[b])
                    {
                        cnt++;
                        tmp.erase(tmp.begin() + b);
                        b--;
                        break;
                    }
                }
            }
            
            if(cnt == stri.size())
            {
                answer++;
            }
        }
    }
    return answer;
}

범위가 크지않아서,, 3중 포문을 썼는데 이게 맞나 싶긴함..