프로그래머스] C++ 완전탐색 - 소수찾기(Level 2)

해당 문제는 프로그래머스 코딩테스트 연습에 있는 문제입니다.

아래 링크를 통해 풀 수 있습니다.

 

 

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

 

 

 

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

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

제한사항

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

입출력 예

numbers	return
17	3
011	2

입출력 예 설명

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

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

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

 

 

 

 

 

저에겐 정말 어려운 문제였습니다.

 

처음엔 주어진 숫자의 조합으로 나올 수 있는 모든 경우의 수를 구한 후 앞자리가 0인 경우를 제외시키고 set에 다 넣은 후

하나씩 꺼내서 경우의 수가 소수인지 아닌지 판단해주는 코드를 작성하려고 했지만, 모든 경우의 수를 어떻게 구해야 할지 감이 잡히질 않아서....

열심히 만들다가 도중에 포기했습니다.

 

그래서 1주일동안 심심할때마다 생각하면서 방도를 찾았습니다.

 

그리고 오늘... 버스를 타고 집에 오는길에 해결방안이 떠올라서 실행에 옮겼고, 저는 성공했습니다. (아주 빠르게)

 

 

 

 

푸는 공식은 다음과 같습니다.

 

1. 문자열 numbers가 주어지면 내림차순으로 정렬해준다.

(이렇게 될 경우 numbers는 가장 큰 숫자로 정렬됩니다.)

 

2. 에라토스테네스의 체를 사용해 정렬된 numbers의 숫자 크기만큼 소수를 모두 구해줍니다.

(예를들어 예제 #2같은 경우 0, 1, 1를 정렬하면 1, 1, 0이 됩니다. 즉, 정수 110이 되죠.

그럼 110까지의 소수를 모두 구해줍니다.)

 

3. 소수를 모두 구하면 처음부터 끝까지 소수 하나하나를 numbers와 비교해 줍니다. 소수를 문자열로 만든 후 말이죠.

(예를들어 예제 #2의 경우 110까지의 소수를 모두 구했으면 2, 3, 5, 7, 11... 이렇게 비교하면서 해당 소수가 1, 1, 0 의 숫자에 

포함 되는지 확인하는 것입니다. 만약 11이라면 1과 1이 numbers에 있는지 확인하는 것입니다.)

 

#include <string>
#include <algorithm>

using namespace std;

int solution(string numbers) {
    int answer = 0;  
    sort(numbers.begin(), numbers.end(), greater<int>());
    int num = atoi(numbers.c_str());
    
    long long * p = new long long[num + 3];
    
    for (int i = 2; i < sqrt(num); i++) {    //에라토스테네스의 체
        if (!p[i]) {
            for (int j = i * i; j <= num; j += i) {
                p[j] = 1;
            }
        }
    }
    
    for(int i  = 2; i <= num; i++){
        if(p[i] == 0){        //소수를 찾았다면....
            int val = i;
            int j;
            char temp[8], orit[8];
            numbers.copy(temp, sizeof temp - 1);    //numbers복사
            temp[numbers.size()] = '\0';
            
            for(j = 0; j < 8; j++){
                orit[j] = (val % 10) + '0';        //소수를 문자열로 변환
                val /= 10;
                if(val == 0)
                    break;
            }
            
            int count = -1;
            for(int x = 0; x <= j; x++){
                for(int y = 0; y < numbers.size(); y++){
                    if(orit[x] == temp[y]){     //소수 문자열이 numbers에 있는지 확인
                        temp[y] = -1;    //중복 숫자 방지
                        count++;
                        break;
                    }
                }
            }
            if(count == j)        //소수 문자열이 numbers에 포함되 있다면....
                answer++;
        }
    }
    delete[] p;
    return answer;
}