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

문제

프로그래머스 완전탐색 - 소수 찾기

코딩테스트 연습 - 소수 찾기

문제 설명

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

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

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.

• numbers는 0~9까지 숫자만으로 이루어져 있습니다.

• 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers	return
17	3
011	2

 

---

문제 풀이

접근 방식

numbers 문자열로 만들 수 있는 모든 수의 조합을 먼저 구해주었다.

우선, numbers의 모든 문자를 숫자로 바꿔 num 벡터에 넣어주고, all_num 셋에도 넣어주었다.

(all_num은 모든 수의 조합을 저장해줄 곳이다. 중복이 없어야 하므로 unordered_set으로 구현하였다.)

num에 들어있는 숫자들로 가능한 숫자 조합을 구하기 위해 next_permutaion을 사용하였다.

do ~ while 문 내에서는 num의 숫자들로 가능한 모든 조합을 all_num에 저장해주는 작업을 수행하였다.

 

위의 과정을 "011"에 적용해보자.

num에는 0, 1, 1이 저장되고, all_num에는 0, 1이 저장된다.

num을 오름차순으로 정렬하고 next_permutation을 수행한다.

첫번째 num은 [0, 1, 1]이다. num의 사이즈는 3이기 때문에 2 ~ 3자리 숫자를 all_num에 넣어준다.

즉, all_num에 01, 011이 들어간다. (1, 11을 삽입해주지만 1은 이미 있으니 11만 추가된다.)

다음 num은 [1, 0, 1]이므로, all_num에 10, 101을 넣어준다.

다음 num은 [1, 1, 0]이므로, all_num에 11, 110을 넣어준다.

이렇게 next_permutation을 수행한 결과, all_num에는 [0, 1, 11, 10, 101, 110] 의 숫자들이 들어있게 된다.

 

모든 수의 조합을 구한 후, check 함수를 만들어 소수인지를 확인하여 답을 도출할 것이다.

all_num의 원소 n이 2 미만이면 넘어가고, 그렇지 않으면 check 함수에 넣어 소수인지를 확인한다.

check 함수는 n을 2 ~ sqrt(n)의 숫자로 나눈 나머지가 0인 경우가 존재하면 false, 그렇지 않으면 true를 반환한다.

즉, 소수이면 true를 반환하고, answer++를 수행하여 최종 답을 도출한다.

 

"011"의 경우, [0, 1, 11, 10, 101, 110]에서 11과 101이 소수이므로 2를 리턴한다.

 

---

풀이 코드 - C++

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

using namespace std;

bool check(int n) {
	int end = sqrt(n);
	for (int i = 2; i <= end; i++) {
		if (n % i == 0)
			return false;
	}
	return true;
}

int solution(string numbers) {
	// 숫자 조합하기
	vector<int> num;
	unordered_set<int> all_num;
	int len = numbers.size();
	for (int i = 0; i < len; i++) {
		num.push_back(numbers[i] - '0');
		all_num.insert(numbers[i] - '0');
	}
	sort(num.begin(), num.end());
	do {
		for (int i = 2; i <= len; i++) {
			string a = "";
			for (int j = 0; j < i; j++) {
				a += num[j] + '0';
			}
			all_num.insert(stoi(a));
		}
	} while (next_permutation(num.begin(), num.end()));

	// 소수인지 확인
	int answer = 0;
	for (int n : all_num) {
		if (n < 2) continue;
		if (check(n))
			answer++;
	}
	return answer;
}

실행 결과