[프로그래머스] 소수 찾기

문제 설명

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

---

오랜만에 푼 완전탐색 문제라 고전했다.

문제는 크게 두 부분으로 나뉜다.

• 소수임을 판별할 수 있는가? 
• 주어진 수로 중복이 없는 가능한 모든 조합을 구할 수 있는가?

소수를 판별하는 것은 수없이 해본 에라토스테네스의 체를 통해 해결했다.

애를 먹은 부분은 모든 조합을 구하는 부분이었다.

한동안 알고리즘 문제풀이를 안했더니 기억이 잘 안났는데, 전에 풀었던 백준 N과 M 문제를 보고 다시 떠올렸다.

 

기억을 되살리니 문제는 쉬워졌다. 각 인덱스에서 numbers에서 고를 수 있는 모든 수를 고른다. 단 이전에 고른 수를 다시 쓸 수는 없기에 visit라는 배열로 사용 여부를 판별했다. 

dfs를 돌며 idx의 길이가 다 되었을 때 cur가 0이 아니며, 소수여야 하고, 중복이 아닐 때 경우의 수를 1 증가했다.

중복 판별여부는 map을 사용했다. 방문했을시 map의 value를 1증가시켜서 중복 여부를 쉽게 판별할 수 있었다.

 

모든 경우의 수를 구하고 반환하면 끝이다.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Programmers/%EC%86%8C%EC%88%98%20%EC%B0%BE%EA%B8%B0.cpp

chosh95/STUDY

C++ 코드

#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <memory.h>
#include <algorithm>
using namespace std;
const int maxNum = 100000001;
bool isPrime[maxNum];
int visit[10];
int cnt;
map<int, int> m;

void eratos() {
	memset(isPrime, true, sizeof(isPrime));
	isPrime[0] = isPrime[1] = false;
	for (int i = 2; i*i < maxNum; i++) {
		if (isPrime[i] == false) continue;
		for (int j = i + i; j < maxNum; j += i)
			isPrime[j] = false;
	}
}

void dfs(string origin, int idx, int cur) {
	if (idx == origin.size()) {
		if (cur == 0) return;
		if (isPrime[cur] && m[cur] == 0) {
			m[cur]++;
			cnt++;
		}
		return;
	}
	dfs(origin, idx + 1, cur);
	for (int i = 0; i < origin.size(); i++) {
		if (visit[i] == true) continue;
		int tmp = cur * 10 + (origin[i]-'0');
		visit[i] = true;
		dfs(origin, idx + 1, tmp);
		visit[i] = false;
	}
}


int solution(string numbers) {
	eratos();
	memset(visit, false, sizeof(visit));

	dfs(numbers, 0,0);

	return cnt;
}

int main()
{
	cout << solution("17");
}