나의 풀이
푸는 데 엄청나게 많은 시간이 들었다. 코드는 신기하게도 짧지만 5시간은 넘게 고민한 것 같다.
대학교 2학년 때 자료구조 과제를 할 때도 재귀함수 부분에서 막혔는데 여기서도 시간이 많이 걸린 걸 보면 내가 재귀함수에 많이 약한 것 같다... 그래도 혼자 힘으로 풀었으니 다음에 마주치면 더 빨리 풀길..!
재귀함수로 풀이를 하기 전에 일단 루프를 만들고 특정 부분을 공식화해서 함수로 빼내보려고 했지만 여기서부터 막혀버렸다.
if(int i = 0; i < size; ++i)
{
if(i>=0)
for(...)
{
//...
if(i>=1)
for(...)
{
//...
if(i>=2)
for(...)
{
//,,,
}
}
}
}이런 꼴의 코드라면 다음부턴 바로 재귀함수를 생각하자!
여기서 0,1,2를 변수로 만들고 싶었지만 그럴 수가 없어서 한참을 고민했다.
고민 끝에 나온 결론이 반복을 줄이지말고 풀어보는 것이었다.
for(...)
{
//...
}
for(...)
{
//...
for(...)
{
//...
}
}
for(...)
{
//...
for(...)
{
for(...)
{
//...
}
}
}이 코드를 보고 재귀함수로 만들어보자고 생각했지만 재귀함수를 많이 만들어 보지 않아서 뜻대로 되지는 않았다.
먼저 가지치기를 그려서 변수들이 어떻게 변하는 지 적어놓고 알고리즘을 짰다.
주어진 문자열이 "178"이라면 가지치기가 이런 모양이 된다.
1 mix = " "
pos = 0
numbers = "178"
/ | \
2 mix = "1 " mix = "7 " mix = "8 "
pos = 1 pos = 1 pos = 1
numbers = "78" numbers = "18" numbers = "17"
/ \
3 mix = "17 " mix = "18 "
pos = 2 pos = 2 ...
numbers = "8" numbers = "7"
|
4 mix = "178" .
pos = 3 .
numbers = "" .
다음은 여러 시행착오 끝에 나온 재귀함수 코드이다.
void mix_func(string mix, int pos, string numbers)
{
if (isdigit(mix[0]) && isPrimeNumber(stoi(mix)))
primenumbers.insert(stoi(mix));
if (pos == mix.size()) return;
for (size_t i = 0; i < numbers.size(); i++)
{
string a = numbers;
string m = mix;
int p = pos;
m[p] = a[i];
a.erase(a.begin() + i);
mix_func(m, ++p, a);
}
}여기서 재귀함수 매개변수로 mix와 pos를 그대로 놓으면 값이 엉뚱하게 나온다.
가지를 올라갈 때 mix와 pos가 이전 값을 유지해야 하는데 변경된 값으로 적용되기 때문이다.
새로운 변수를 각각 만들어서 해결했다.
그 다음은 앞에서 조합으로 나온 수 중에서 소수의 개수를 구해야 된다.
중복을 허용하지 않기 위해 set에 전부 담았다.
static set<int> primenumbers;소수를 검사하는 알고리즘은 간단하다. 숫자들 모임이 아니라 하나씩 검사해야 하기 때문에 '에라토스테네스의 체'를 적용하지는 않았다.
bool isPrimeNumber(int num) {
if (num == 0 || num == 1) return false;
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}🎉완성코드
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <iostream>
using namespace std;
static set<int> primenumbers;
bool isPrimeNumber(int num) {
if (num == 0 || num == 1) return false;
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
void mix_func(string mix, int pos, string numbers)
{
if (isdigit(mix[0]) && isPrimeNumber(stoi(mix)))
primenumbers.insert(stoi(mix));
if (pos == mix.size()) return;
for (size_t i = 0; i < numbers.size(); i++)
{
string a = numbers;
string m = mix;
int p = pos;
m[p] = a[i];
a.erase(a.begin() + i);
mix_func(m, ++p, a);
}
}
int solution(string numbers) {
primenumbers.clear();
string mix;
mix.resize(numbers.size());
mix_func(mix, 0, numbers);
return primenumbers.size();
}
int main()
{
cout << solution({ "178" }) << endl;
cout << solution({ "011" }) << endl;
}추천을 가장 많이 받은 풀이
이번 문제는 내가 푼 코드가 훨씬 빠르고 코드도 더 짧아서 생략하겠다.
