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

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

문제 링크 : 소수찾기

코딩테스트 연습 - 소수 찾기

 

문제 설명

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

 

---

풀이과정

1. 문제 이름부터가 소수 찾기임
2. 그 말은 즉슨, 에라토스테네스의 체 를 이용하여 푸는 방법이라고 직감함 => 이런거 학부때는 몰랐는데(공부를 드럽게 안해서) 취준할 때 용일이라는 친구가 알려줌. 어차피 이 글 볼리는 없을테니 고맙다는 말은 안할 예정. 아 몰라 그냥 안할 예정.
3. 에라토스테네스의 체 를 이용하여 처음에는 bool 타입의 배열에다가 해당 숫자(인덱스)가 소수인지만 체크하는 식으로 진행함.
4. 근데 next_permutation 으로 모든 수들의 조합을 구하다 보면 중복되는 숫자가 나오기 때문에 만약 같은 숫자를 체크하게 된다면 카운팅을 두번하게 되는것을 늦게 깨달음
5. 다시 int 타입으로 바꾸고 한번 체크한 수는 값을 2로 바꿔줌으로서 중복 체크까지 하도록 처리
6. string 타입으로 들어오는 numbers의 모든 가지수를 구하는 것에서 next_permutation 을 두번 써서 효율성에서 걸리지 않을까라는 생각을 했으나, 통과되었음
7. 11과 011 같은 경우에는 똑같은 숫자로 취급되고, 다른 경우에도 0이 가장 맨 앞에 있는 경우는 재끼기 위해 조건을 하나 걸어줌(62번째줄)

 

코드

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

using namespace std;

#define MAX 9999999

int isPrime[MAX+1];

void sieveOfEratosthenes(int n) {
    for(int i = 2; i <= n; i++) {
        isPrime[i] = 1; // n까지 일단 초기화
    }

    int sqrtn = sqrt(n); // 루트까지만 검사를 해줘도 약수 여부 판단 가능
    for(int i = 2; i <= sqrtn; i++) {
        if(isPrime[i] == 0)
            continue;

        for(int j = i + i; j <= n; j += i) { // 소수가 아닌 것들을 0으로 지워나가면서 진행
            isPrime[j] = 0;
        }
    }
}

int solution(string numbers) {
    int answer = 0;

    sieveOfEratosthenes(MAX);

    int numLen = (int)numbers.length();
    int numPos = 1; // 자릿수

    while(numPos <= numLen) {
        vector<int> comb;

        for(int i = 0; i < numPos; i++) {
            comb.push_back(1);
        }

        for(int i = 0; i < numLen-numPos; i++) {
            comb.push_back(0);
        }

        sort(comb.begin(), comb.end());

        do {
            string temp;

            for(int i = 0; i < numLen; i++) {
                if(comb[i] == 1) {
                    temp += numbers[i];
                }
            }

            sort(temp.begin(), temp.end());

            do {
                if(temp[0] == '0')
                    continue;

                int num = stoi(temp);

                if(isPrime[num] == 1) {
                    isPrime[num] = 2;
                    answer++;
                }
            }while(next_permutation(temp.begin(), temp.end()));

        }while(next_permutation(comb.begin(), comb.end()));

        numPos++;
    }

    return answer;
}