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

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소입니다.

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

불러오는 중입니다...

 

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

3.1 주석 없는 코드

3.2 주석 있는 코드

3.3 테스트 코드

4. 결과

 

---

1. 문제 설명

 

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

 

문제!!

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

 

제한사항

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

 

예시

Numbers	return
"1"	3
"011"	2

 

 

예제 #1 [1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다. 예제 #2 [0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다. 11과 011은 같은 숫자로 취급합니다.

 

---

2. 문제풀이

이 문제의 핵심은 모든 경우의 수를 만들 수 있느냐 와 소수판별입니다. numbers로 들어오는 숫자를 이용하여 모든 경우의 수를 만들고 각각 소수를 판단하여 소수일경우 answer를 증가시켜 리턴하면 되는 문제입니다.   경우의 수를 판단하기 위해서는 저는 이렇게 했습니다. 문자열을 각각 쪼개서 char형으로 만든후 bool형과 함께 pair로 묶었습니다. 어떤 수를 사용했으면 사용했다고 표시해야 하기 때문입니다. 이후 재귀함수를 이용하여 경우의 수를 만듭니다. set은 중복을 방지하기 위해서 사용했습니다.   두번째로 만들어진 경우의 수를 소수판단을 해야합니다. 소수판단은 여러가지 방법이 있지만 연산을 적게하기 위해서는 루트를 취한값까지 나머지연산을 해보는것입니다. 나머지연산을 해서 0으로 떨어지면 소수가 아니기 때문입니다. 그리고 이방식을 이용하려면 0,1은 예외처리를 해주어야 합니다.

 

---

3. 소스코드

3.1 주석없는 코드

#include <vector>
#include <string>
#include <algorithm>
#include <set>
using namespace std;
 
void push(vector<pair<char, bool>> piece, set<int>& p, string a = "", int cnt = 0) {
    for (int j = 0; j < piece.size(); j++) {
        if (!piece[j].second) {
            piece[j].second = true;
            a += piece[j].first;
            p.insert(stoi(a));
            cnt++;
        }
        else    continue;
        if (cnt != piece.size())    push(piece, p, a, cnt);
        piece[j].second = false;
        a = a.substr(0, a.length() - 1);
        cnt--;
    }
}
 
bool Decheck(int a) {
    for (int i = 2; i <= sqrt(a); i++)
        if (a % i == 0)        return false;
    return true;
}
 
int solution(string numbers) {
    int answer = 0;
    vector<pair<char, bool>> piece;
    set<int> p;
    for (int i = 0; i < numbers.length(); i++)    piece.push_back({ numbers[i], false });
    push(piece, p);
    for (auto c : p) {
        if (c == 0 || c == 1)    continue;
        if (Decheck(c))        answer++;
    }
    return answer;
}

 

3.2 주석있는 코드

#include <vector>
#include <string>
#include <algorithm>
#include <set>
using namespace std;
 
//경우의 수 찾기용, 경우의 수 담기용, 문자열 합치기용
void push(vector<pair<char, bool>> piece, set<int>& p, string a = "", int cnt = 0) {
    //처음붙터 끝까지 반복문을 돌린다.
    for (int j = 0; j < piece.size(); j++) {
        //j인덱스에 관련된 piece가 사용중이지 않다면
        if (!piece[j].second) {
            //사용중으로 변경
            piece[j].second = true;
            //문자열 추가
            a += piece[j].first;
            //현재 문자열을 경우의 수에 담기
            p.insert(stoi(a));
            cnt++;
        }
        else//사용중이라면 위로 보내기
            continue;
        //모두 사용중이 아니라면 재귀
        if (cnt != piece.size())    push(piece, p, a, cnt);
        //사용을 완료하면 사용하지 않음으로 바꾸기
        piece[j].second = false;
        //돌아가기 전에 문자열을 하나 감소
        a = a.substr(0, a.length() - 1);
        cnt--;
    }
}
 
bool Decheck(int a) {
    for (int i = 2; i <= sqrt(a); i++)
        if (a % i == 0)//i가 나누어떨어지면 소수가 아님 
            return false;
    return true;
}
 
int solution(string numbers) {
    int answer = 0;
    //모든 경우의 수를 찾기 위한 용도
    vector<pair<char, bool>> piece;
    //모든 경우의 수를 모으는 곳
    set<int> p;
    //반복문으로 numbers를 쪼개서 piece에 집어넣는다.
    for (int i = 0; i < numbers.length(); i++)
        piece.push_back({ numbers[i], false });
    //모든 경우의 수 찾기
    push(piece, p);
    for (auto c : p) {
        //0과 1인경우는 소수에서 제외
        if (c == 0 || c == 1)    continue;
        //소수를 체크해서 소수면 카운트 증가
        if (Decheck(c))        answer++;
    }
    return answer;
}

3.3 테스트 코드 추가

#include <vector>
#include <string>
#include <iostream>//메인 출력용
#include <algorithm>
#include <set>
using namespace std;
 
//경우의 수 찾기용, 경우의 수 담기용, 문자열 합치기용
void push(vector<pair<char, bool>> piece, set<int>& p, string a = "", int cnt = 0) {
    //처음붙터 끝까지 반복문을 돌린다.
    for (int j = 0; j < piece.size(); j++) {
        //j인덱스에 관련된 piece가 사용중이지 않다면
        if (!piece[j].second) {
            //사용중으로 변경
            piece[j].second = true;
            //문자열 추가
            a += piece[j].first;
            //현재 문자열을 경우의 수에 담기
            p.insert(stoi(a));
            cnt++;
        }
        else//사용중이라면 위로 보내기
            continue;
        //모두 사용중이 아니라면 재귀
        if (cnt != piece.size())    push(piece, p, a, cnt);
        //사용을 완료하면 사용하지 않음으로 바꾸기
        piece[j].second = false;
        //돌아가기 전에 문자열을 하나 감소
        a = a.substr(0, a.length() - 1);
        cnt--;
    }
}
 
bool Decheck(int a) {
    for (int i = 2; i <= sqrt(a); i++)
        if (a % i == 0)//i가 나누어떨어지면 소수가 아님 
            return false;
    return true;
}
 
int solution(string numbers) {
    int answer = 0;
    //모든 경우의 수를 찾기 위한 용도
    vector<pair<char, bool>> piece;
    //모든 경우의 수를 모으는 곳
    set<int> p;
    //반복문으로 numbers를 쪼개서 piece에 집어넣는다.
    for (int i = 0; i < numbers.length(); i++)
        piece.push_back({ numbers[i], false });
    //모든 경우의 수 찾기
    push(piece, p);
    for (auto c : p) {
        //0과 1인경우는 소수에서 제외
        if (c == 0 || c == 1)    continue;
        //소수를 체크해서 소수면 카운트 증가
        if (Decheck(c))        answer++;
    }
    return answer;
}
 
void print(string a, int answer) {
    int t = solution(a);
    if (t == answer)        cout << "정답" << endl;
    else    cout << "틀림" << endl;
}
 
int main() {
    print("17");
    print("011");
    return 0;
}

---

4. 결과