[ 프로그래머스-lv2 / 완전탐색 ] 소수 찾기

1. 문제

---

프로그래머스

• 소수 찾기

• darklight

  sublimevimemacs

  C++ 

문제 설명

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

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

제한사항

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

입출력 예

numbersreturn

17	3
011	2

입출력 예 설명

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

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

 

 

 

2. 소스코드

---

1회차

 

- 풀고도 찝찝한 코드. 1717과 같이 중복되는 수가 있는 경우, 경우의 수에 중복이 생긴다. 이에 마지막에 중복을 제거하는 코드를 넣었음.

 

- 입력 string numbers가 커지면, 무조건 터질 코드.

 

- 예상 시간 복잡도

(nC1 x 1!) + (nC2 x 2!) + (nC3 x 3!) ......+ (nCn x n!)

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

bool isPrime(string num) {
	if (num[0] == '0') return false;
	int number = stoi(num);
    if (number < 2) return false;
	for (int i = 2; i * i <= number; i++) {
		if (number % i == 0) return false;
	}
	return true;
}

int solution(string numbers) {
   
	vector<string> answer;
	vector<int> idx(numbers.size(),0);

	for (int i = 0; i < numbers.size(); i++) {
		idx[0] = 1; sort(idx.begin(), idx.end());
		do {
			string temp = "";
			for (int j = 0; j < numbers.size(); j++) {
				if (idx[j]) {
					temp += numbers[j];
				}
			}
			sort(temp.begin(), temp.end());
			do {
				if (isPrime(temp)) {
					cout << temp << '\n';
					answer.push_back(temp);
				}
			} while (next_permutation(temp.begin(), temp.end()));
		} while (next_permutation(idx.begin(), idx.end()));
	}
	
	sort(answer.begin(), answer.end());
	answer.erase(unique(answer.begin(), answer.end()),answer.end());

	return answer.size();
}

테스트 10 〉

통과 (0.43ms, 3.83MB)

 

2회차

 

- set을 이용하면 중복없이 저장가능.

- substr을 이용해 간편하게 작성했으나, 1회차에 비해 중복 횟수가 훨씬 많아짐.

- 1회차 보다 메모리/시간이 더 안좋은 코드.

 

 
#include <vector>
#include <set>
#include <algorithm>
#include <string>

using namespace std;

int isPrime(int num) {
	if (num < 2) return -1;
	for (int i = 2; i * i <= num; i++)
		if (num % i == 0) return -1;

	return 1;
}

int solution(string numbers) {
 
	set<int> answer;
	sort(numbers.begin(),numbers.end(),greater<char>());
	int max = stoi(numbers);
	sort(numbers.begin(), numbers.end());
	vector<int> primes(max + 1, 0);
 
	do { 
		string temp;
		for (int i = 1; i <= numbers.size(); ++i) {
			temp = numbers.substr(0, i);

			if (primes[stoi(temp)] == 0) {
				primes[stoi(temp)] = isPrime(stoi(temp));
			}
			if (primes[stoi(temp)] == 1) {
				answer.insert(stoi(temp));
			}
			else continue;
		}
	} while (next_permutation(numbers.begin(),numbers.end()));
	 
	return answer.size();
}

테스트 8 〉

통과 (6.21ms, 24.7MB)