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

jh Seo·2023년 7월 18일

브루트 포스 프로그래머스 한번에 못 푼 문제

프로그래머스

목록 보기

22/33

개요

프로그래머스 : 소수찾기

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

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

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

접근 방식

기본적으로 재귀를 통해 완전탐색방식을 떠올렸다.
만들 수 있는 모든 조합을 만든 후, 해당 숫자들을 set에 다 insert한다.
마지막에 set을 순회하며 내부의 숫자들이 소수인지 판별한다.
모든 조합을 찾는 방식을 까다롭게 구현했는데 일단 재귀함수의 인자로
현재 상태의 string형 변수와 기존 string형 변수 이렇게 두개를 받는다.
그 후 각 재귀함수 진입할 때마다 set에 curNum값을 int형으로 변환후 insert한다.
```
void BackTracking(string curNum,string numbers){
    totalNumbers.insert(stoi(curNum));
```
numbers값을 저장할 string형 변수 tmpNumbers를 선언해준 후,
복사해준다.
그 후, tmpNumbers에서 curNum변수와 중복되는 char변수들을 모조리 빼준다.
이렇게 해야 현재 단계에서 아직 안 들린 char형 값들을 알 수 있다.
```
   string tmpNumbers=numbers;
   for(char elem : curNum){
       tmpNumbers.erase(find(tmpNumbers.begin(),tmpNumbers.end(),elem));
   }
```
tmpNumbers에 남아있는 char형 값들이 이제 진행해야할 경로이다.
```
   for(char elem : tmpNumbers){
       curNum+=elem;
       BackTracking(curNum,numbers);
       curNum.pop_back();
   }
```
curNum에 tmpNumber안의 char원소를 추가한 후
다음 재귀함수로 진입한다.
빠져나왔다면 다시 for문으로 가서 다른 char원소로 진행해야하므로
pop_back을 통해 curNum을 들어가기 전 상태로 초기화해준다.
그 후, set을 순회하며 prime Number값을 판별했다.
판별하는 방법은 무식하게 2부터 N-1까지 나눠서 판별했다.
밑의 문풀후생에 후술할 방법인 에라토스테네스의 체를 사용하는 방식이 더 효율적이다.
문제는 계속 signal aborted(core dumped)오류가 나와서
매우 당황했는 데, 코드상으로는 아무리 보고 직접 써가며 분석해도
헛도는 곳이 없어서 긴 시간을 고민했다.

결국 포기하고 다른 코드들을 참고했는데 바로 알 수 있었다,,
현재 curNum값을 set에 넣어주는 부분을
```
    totalNumbers.insert(stoi(curNum));
```
이런식으로 stoi함수를 사용한다.

문제는 초기값으로 curNum값을 빈스트링 값인 ""로 넣어줘서
stoi()함수 인자로 ""가 들어가서 오류가 나는 것이였다!!
```
if(curNum!="")
totalNumbers.insert(stoi(curNum));
```
이런식으로 조건문 붙여주니 잘 되었다.

전체 코드

#include <string>
#include <vector>
#include <set>
#include <iostream>
#include<algorithm>
#include<math.h>

using namespace std;
set<int> totalNumbers;

void BackTracking(string curNum,string numbers){
    if(curNum!="") 
        totalNumbers.insert(stoi(curNum));
    if(curNum.length() ==numbers.length()) return;
    string tmpNumbers=numbers;
    for(char elem : curNum){
        tmpNumbers.erase(find(tmpNumbers.begin(),tmpNumbers.end(),elem));
    }
    for(char elem : tmpNumbers){
        curNum+=elem;
        BackTracking(curNum,numbers);
        curNum.pop_back();
    }
}



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

int GetPrimeNumberAmount(){
    int Ret=0;
    for(auto num : totalNumbers){
        if(IsPrime(num)){
         cout<<num<<" ";   
        Ret++;
        }
    }
    return Ret;
}

int solution(string numbers) {
    int answer = 0;
    string curNum="";
    BackTracking(curNum,numbers);
    answer=GetPrimeNumberAmount();
    return answer;
}

문풀후생

제일 먼저 해멘 부분은 string값에서 해당 원소를 탐색 후 지우는 부분이였다.

string.erase(char a)

이렇게 사용하면 string.substr(char a)와 동일하게 작동한다. a 찾은 후 뒤에값들을 전부 날려버린다.
인자로 char형이 아니라, iterator을 넣어야 내가 원하는 대로 해당 원소를 삭제한다.

아무생각없이 string.find도 set.find처럼 iterator을 반환하겠거니 했으나 아니였다..
string.find는 해당 원소의 인덱스를 반환하는 것이였고,
따라서 string.erase(string.find('3'))이런 식으로 짜게되면,
해당 string의 3이 있는 위치부터 뒤를 날려버리는 식이라
내가 원하는 대로 3만 지울 수 없게된다.

해결방식은 string.find가 아닌 algorithm헤더의 find를 사용해야 한다.
find함수를 보면

Returns an iterator to the first element in the range [first,last) that compares equal to val. If no such element is found, the function returns last.

이런 식으로 시작 iterator과 끝 iterator을 넣어준 후, 찾으려는 element값을 인자로 넣어주면 해당 element 위치의 iterator을 반환한다.

더 간결한 완전탐색 함수

다른 풀이를 보다가 발견한건데 내 BackTracking함수를 훨씬 간결하게 작성할 수 있었다.

번거롭게 curNum에 해당하는 char원소를 tmpNumbers에서 검색해서 지우지 않고 그냥 substr을 통해 관리할 수 있다!!

void DFS(string curNum, string numbers)
{
    if (curNum != "")
        totalNumbers.insert(stoi(curNum));

    for (int i = 0; i < numbers.size(); i++)
        DFS(curNum + numbers[i], numbers.substr(0, i) + numbers.substr(i + 1));
}

이런식으로 짠다면 tmpNumber에서 curNum을 순회하며 해당 값을 찾아서 지우는 연산도 안 해도되며 push,pop연산도 안할 수 있다.
매 재귀마다 깔끔하게 한글자씩 numbers에서 빼며 진행하는 것이다.

내가 짠 방식도 push,pop연산을 줄일 수 있다.

for(char elem : tmpNumbers){
	BackTracking(curNum+elem,numbers);
}

이렇게 고친다면 더 연산이 줄어들어 효율적이다.

에라토스테네스의 체

또한 에라토스테네스의 체라는 방식을 사용할 수 있다.
에라스토테네스의 체는 어떤 값(x라고 하자)의 소수를 구할때 사용되며,
모든 수로 다 나눠보지 않고 , 루트 x보다 작은 값들만 나눠보며 판별하는 방식이다.

이게 가능한 이유는
예를 들어 12는 1 * 12, 2 * 6, 3 * 4, 4 * 3, 6 * 2, 12 * 1
이런 식으로 약수들이 순서만 바꿔서 짝을 이뤄 존재한다.
따라서 루트 12보다 작은 수 중 최대값인 3까지만 나눠보면 된다.
3 이상의 약수는 이미 구한 앞의 약수와 쌍을 이루기 때문이다.

따라서 소수를 구할때 지금은 2부터 N-1값을 다 나눠보지만,
2부터 N의 제곱근값까지만 나눠서 소수인지만 판별해도 충분하다.