[Programmers Level2] 소수 찾기(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은 같은 숫자로 취급합니다.

 

[문제 풀이]

 

문자열을 자료형이 int인 vector에 저장하기 위해

1. int형 vector를 생성한다.

2. vector에 push_back하여 넣을 때 문자 - '0' 을 하여 숫자(0 ~ 9)가 저장될 수 있도록 했다.

 

그리고 경우의 수를 구하기 위해 next_permutation을 사용했다.

next_permutation 사용을 위해 숫자를 저장한 vector를 오름차순으로 정렬했다.

하지만 경우의 수를 구하는데, 자릿수가 1자리, 2자리 .. 최대 7자리까지 구해야했다.

 

그래서 자리수에 따른 경우의 수를 구하기 위해

1. do-while문 위에 for문을 사용

2. vector<bool> temp를 생성 시 총 길이 - 구하고자하는 자리수 크기만큼 만들고 false로 초기화

3. temp vector의 끝에 구하고자 하는 자리수 크기만큼을 true 값으로 삽입

4. temp vector의 원소가 true인 경우에만 vector값을 string화 하여 저장

 

그리고 저장한 string을 길이가 1일 때(0 ~ 9의 경우)와  길이가 1이 아닐때의 경우를 나누어서 소수 판별을 하였다.

또한, 소수 판별을 할 때, 중복값 확인을 위해 만든 크기가 10000000인 arr 배열이 0일 때만 판별할 수 있도록 했다.

이유는 소수 판별이 완료되면 arr[소수 판별된 값] 을 1 증가 시켜줌으로서 중복된 값을 제외할 수 있기 때문이다.

 

 

[C++ 순열과 조합] next_permutation

 

[최종 코드]

 

[GitHub]

 

GitHub - SmallPeanutPark/Programmers: Study Programmers for Coding Test

 

 

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

int arr[10000000] = { 0, }; // 중복 확인 배열

bool isPrime(int number) {

    if (number < 2) {
        return false;
    }

    for (int i = 2; i <= sqrt(number); ++i) {
        if (number % i == 0) {
            return false; // 소수 아님
        }
    }
    return true;
}

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

    for (int i = 1; i <= len; ++i) {
        vector<bool> temp(len - i, false);
        temp.insert(temp.end(), i, true);
        do {
            string s;
            for (int j = 0; j < len; ++j) {
                if (temp[j]) {
                    s += to_string(numvector[j]);
                }
            }
            int slength = s.length();
            if (slength == 1) {
                if (arr[s[0] - '0'] == 0) {
                    if (isPrime(s[0] - '0')) {
                        ++answer;
                        arr[s[0] - '0']++;
                    }
                }
            }
            else {
                if (arr[stoi(s)] == 0) {
                    if (isPrime(stoi(s))) {
                        ++answer;
                        arr[stoi(s)]++;
                    }
                }
            }

        } while (next_permutation(numvector.begin(), numvector.end()));
    }
    return answer;
}