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

Juppi·2021년 9월 29일

C algorithm python 소수찾기 순열 알고리즘 에라토스테네스의 체 완전 탐색 프로그래머스

Algorithm

목록 보기

2/4

오늘의 문제는 완전탐색을 이용하여 풀 수 있는 소수찾기이다
문제는 아래와 같다 !

소수 찾기

문제 설명

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

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

제한사항

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

입출력 예 설명

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

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

문제 풀이

가장 먼저 떠오른 문제 풀이로는 주어진 숫자 문자열의 진부분집합의 모든 순열을 구해서,
소수 판별 알고리즘인 에라토스테네스의 체를 사용하여 소수 여부를 확인하고,
"11"과 "011" 같은 중복된 요소를 제거하기 위해 set 자료구조에 넣어서 푸는 방법이다.

위 풀이 과정을 그대로 c++ 및 파이썬 코드로 옮겨적었다.

순열을 구하는 알고리즘을 직접 짜야하나 고민했는데, 검색해보니 C++과 Python 모두 순열을 구해주는 라이브러리가 존재해서 쉽게 풀 수 있었다. 참고한 블로그는 맨 아래에 적어두었다.

코드

C++ 코드

#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_set>

using namespace std;

bool isPrime(int n);

int solution(string numbers) {
    
    // 중복 방지를 위한 집합 자료구조 
    unordered_set<int> answer;
    int temp=0;
    do {
        for (int i=1; i<numbers.size()+1; i++){
            
            // 가능한 숫자의 조합을 모두 만들기위해 substr로 숫자의 길이를 변형
            temp = stoi(numbers.substr(0, i));
            if (isPrime(temp))
                answer.insert(temp);
        }
    // next permutation 함수를 이용해 numbers의 값들을 다음 순열로 바꿈
    } while(next_permutation(numbers.begin(), numbers.end()));
    
    return answer.size();
}

bool isPrime(int number){
    if (number <= 1) 
        return false;
    
    for (int i=2; i<=sqrt(number); i++){
        if (number % i == 0)
            return false;
    }
    return true;
}

Python 코드

import itertools
import math

def solution(numbers):
    answer = set()
    
    for i in range(1, len(numbers)+1):
        # itertools.permutations는 결과값을 튜플 오브젝트로 반환하기 때문에 string list로 바꿔줌
        permutation_list = list(map(''.join, itertools.permutations(numbers, i)))
        
        for p in range(len(permutation_list)):
            if is_prime(int(permutation_list[p])):
                answer.add(int(permutation_list[p]))
        print(answer)
    return len(answer)


def is_prime(number):
    if number <= 1:
        return False
    
    for i in range(2, int(math.sqrt(number))+1):
        if number % i == 0:
            return False
        
    return True