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

문제

 

 

 

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

using namespace std;

bool check_prime(int _Number)
{
     if (_Number < 2)       // 0, 1은 소수 아님
        return false;
 
    for(int i=2; i<=_Number/2; i++)
    {
        if(_Number%i ==0)
            return false; 
    }
    
    return true; 
}

void DFS (int _iCount, string _CurString, string _GiveString, set<int>& _Result, vector<bool>& _visited)
{
    if(_iCount == _GiveString.size())
    {
        if(_CurString == "")
            return;
        
        int Number = stoi(_CurString);
        
        if(check_prime(Number))
        {
            _Result.insert(Number);
        }
        
    }
        
    
    else
    {
        for(int i=0; i< _GiveString.size(); i++)
        {
            if(_visited[i])
                continue; 
        
            _visited[i] =true; 
            DFS(_iCount+1 ,_CurString, _GiveString, _Result, _visited);
            DFS(_iCount+1 ,_CurString + _GiveString[i], _GiveString, _Result, _visited);
            _visited[i] =false; 
        }
        
        
    }
    
    
    
}




int solution(string numbers) 
{
    int answer = 0;
    
    vector<bool> m_visited(7,false); 
    set<int>  m_set;
    
    int i_Count =0;

 
    
    DFS(i_Count, "", numbers, m_set, m_visited);   
    
    answer = m_set.size();
    
    return answer;
}

 

 

문제 접근 순서 

 

1. 문제를 보아하니 모든 숫자를 한번씩 다 정렬해서 생각해야 하므로 완전탐색을 생각했고 그 중 순열이니 DFS 구조를 생각했다. 

 

2. DFS 구조는 완전탐색 알고리즘 중 하나로 재귀함수를 통해 구현하였다. 

 

3. 이 문제의 핵심은 소수 찾기 구현 보다는 순열에 대한 알고리즘을 설정할 수 있는가에 대한 문제인 것으로 생각되어

    직접 막상 구현할려니 어려웠지만, 차근차근 연습장에 적어보니 재귀함수의 형태를 생각할 수 있었다.

    간단하게 2개의 원소로만 이루어졌을때 어떻게 해야할지를 고민하면 풀린다. 

 

4. 소수 찾기 알고리즘에서 주의할 것으로는 0과 1은 소수가 아니라는점 그리고 2일때  반복문 조건에 안맞아서 안들어가는 경우가      생기므로 = 표시를 넣어줄것!

 

 

 

    

Plus) 재귀 함수에 대한 설명

 

ex) "123" 이라면

        첫 단계 " "-> " "  ( i_Count = 1)  ->  0( i_Count = 2) -> 0 (i_Count =3) 으로 끝나면서 ( 재귀함수 반복되면서)  소수체크

        첫 단계  "1" ->"1" (i_Count =1 ) ->  1(i_Count =2) -> 1 (i_Count =3) 으로 끝나면서 소수체크 

                 - 두 번째 단계 : 해당 원소를 방문했는지를 체크  "2" -> (i_Count =1) -> 위 과정과 마찬가지로 진행

         

       해당 for문의 한 사이클이 끝나면 다시 이제 2자리부터 시작 하면서 이전에 방문한 노드 기록들 다시 초기화. 

       총 벡터의 사이즈만큼의 ex)"12345" 라면 총 5자리수니깐 0~5까지 반복 

 

 

 

next_permutation을 이용한 방법

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

using namespace std;

bool check_prime(int _Number)
{
     if (_Number < 2)       // 0, 1은 소수 아님
        return false;
 
    for(int i=2; i<=_Number/2; i++)
    {
        if(_Number%i ==0)
            return false; 
    }
    
    return true; 
}


int solution(string numbers) 
{
    int answer = 0;
    
    sort(numbers.begin(),numbers.end());
    
    set<int> m_set; 

    do
    {
        string temp; 
        for(int i=0; i< numbers.size(); i++)
        {
           temp += numbers[i]; 
           if(check_prime(stoi(temp)))
               m_set.insert(stoi(temp));
        }
    }
    while(next_permutation(numbers.begin(), numbers.end()));
    
    
    answer = m_set.size();
    
    return answer;
}

 

 

문제 접근 순서 

 

1. next_permutation을 활용한 순열 경우의 수 나타내기 ( 주의할 점으로는 반드시 오름차순으로 정렬해야한다) 

   그 이유는 현 배열의 상태를 기준으로 오름차순으로 만들기 때문. 

 

2. 각 자리수마다 비교를 해야하므로 for문을 통해 각 자리마다 소수인지 체크하고 중복 체크를 위해 set 컨테이너를 사용 

 

3. set 컨테이너의 크기만큼이 정답.

 

 

 

문제를 풀고 나서 한가지 아쉬운점 및 잘못한점

- 소수를 찾을 때

bool is_Prime(int _Numbers)
{
	if (_Numbers < 2)
		return false; 
	
	
	for(int i=2; i<=_Numbers/2; i++)
	{
		if(_Numbers%i == 0)
		{
			return false; 
		}
	}

	return true; 

}

이 코드 보다는

bool is_Prime(int _Numbers)
{
	if (_Numbers < 2)
		return false; 
	
	
	for(int i=2; i*i<=_Numbers; i++)
	{
		if(_Numbers%i == 0)
		{
			return false; 
		}
	}

	return true; 

}

이 코드가 훨씬 효율적이다

 

 

그 이유는 바로 제곱근을 기준으로 배수가 대칭이기 때문이다. 

 

참고 자료

 

다음 사진과 같이 36을 예로 들면 36의 제곱근 6을 기준으로 위 아래가 대칭인 점을 볼 수 있다.

즉 제곱근까지만 체크를 한다면 해당 수가 소수인지 아닌지를 판별할 수 있다는 점이다.