프로그래머스 - 소수 찾기(Level 2)/Wanna Be 컴잘알

문제 출처 - https://programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기 | 프로그래머스

- 문제 -

문제 설명

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

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

제한사항

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

입출력 예

17	3
011	2

 

- 접근 -

 

1. 주어진 number문자열로 만들 수 있는 모든 순열을 체크해봐야한다. 따라서 n개( 1~number.length() )의 갯수로 이루어진 순열을 다 찾아보기 위해서 반복문 안에 재귀함수를 돌렸다.

2.  011인 경우에 1,01,10 등 중복되는 순열이 만들어진다. 따라서 set 자료구조(중복을제거 하는 특징)를 사용하였다.

 

- 후기 -

 

1. 재귀함수내에서 set에 저장하는 방법은 중복체크를 해주는 편한 방법이지만 큰 메모리가 필요하다.

 

- 코드 -

C++

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

set <int> s;
vector<int> v;
bool check[7];

void solve(int cnt, int end, string numbers) {
	
	if (cnt == end) {
		int multi = 1;
		int result = 0;
		for (int i = v.size()-1; i >=0; i--) {
			result += multi * v[i];
			multi *= 10;
		}
		s.insert(result);
		// 숫자로 바꿔서 넣어야한다.
		return;
	}
	
	for (int k = 0; k < numbers.size(); k++) {
		if (!check[k]) {
			check[k] = true;
			v.push_back(int(numbers[k])-'0');
			solve(cnt + 1, end, numbers);
			v.pop_back();
			check[k] = false;
		}
	}
}


int solution(string numbers) {
	int answer = 0;
	v.clear();
	for (int i = 1; i <= numbers.length(); i++) {
		solve(0, i, numbers);
	}

	for (auto s_item : s) {
		
		bool flag = false;
		if (s_item == 0 || s_item == 1) {
			continue;
		}

		for (int k = 2; k <= s_item / 2; k++) {
			if (s_item%k == 0) {
				flag = true;
				break;
			}
		}
		if (!flag) {
			answer++;
		}
	}
	return answer;
}

Python 3 (추가 업로드)

check=[]
vector=[]
set1 = set()

def isSosu(num):
    sosu = True
    if num ==1 or num==0:
        return False

    for i in range(2,int(num/2)+1,1):
        if num%i==0:
            sosu = False
            break
    return sosu
    
def exchange(vector):
    str1 =""
    for k in vector:
        str1 = str1 +k
    return int(str1)

def solve(numbers, cnt, end):
    global check,vector,set1

    if cnt == end:
        num = exchange(vector)
        set1.add(num)
        return

    for i,value in enumerate(numbers):
        if check[i] == False:
            check[i] = True
            vector.append(value)
            solve(numbers,cnt+1,end)
            vector.pop()
            check[i] = False 

def solution(numbers):
    global check,vector,set1
    answer=0
    for end in range(1,len(numbers)+1,1):
        check = [False for i in range(0,7,1)]
        vector = []
        solve(numbers, 0, end)
    for k in set1:
            if isSosu(k):
                answer+=1
    return answer