소수 찾기

문제

• 완전 탐색 > 소수 찾기

문제 풀이

using System;
using System.Linq;
using System.Collections.Generic;

public class Solution 
{
    public int solution(string numbers) 
    {
        // 중복 제거를 위한 HashSet<int>
        HashSet<int> hashValue = new HashSet<int>();
        // 소수 개수
        int primeCount = 0;
        // 문자 배열
        char[] digits = numbers.ToCharArray();
        
        // 소수는 1보다는 커야해서 1부터 시작해유
        // digits를 돌면서 모든 순열을 생성합니다.
        for(int i = 1; i <= digits.Length; i++)
        {
            Permute(digits,0,i,hashValue,new bool[digits.Length],new List<char>());
        }
        
        // 소수 개수 구하기
        foreach(var pair in hashValue)
        {
            if(isPrime(pair) == true)
                primeCount++;
        }
        
        return primeCount;
    }
    
    // 순열 구하기 (재귀)
    public void Permute(char[] digits, int start, int length, HashSet<int> hashValue, bool[] used, List<char> current)
    {
    	// 개수가 length에 도달하믄
        if(current.Count == length)
        {
            string temp = new string(current.ToArray());
            hashValue.Add(int.Parse(temp));
            return;
        }
        
        // 재귀 돌면서 찾기
        for(int i = 0; i < digits.Length; i++)
        {	
        	// 사용 여부 체크
            if(used[i] == false)
            {
                used[i] = true;
                current.Add(digits[i]);
                
                Permute(digits,i+1,length,hashValue,used,current);
                
                // 백트래킹
                current.RemoveAt(current.Count - 1);
                used[i] = false;
            }
        }
    }
    
    
    // 조건 체크
    public bool isPrime(int num)
    {
    	// 2보다 작으면 소수 아님
        if(num < 2) return false;
       	// 2면 유일한 짝수 소수임
        if(num == 2) return true;
        // 그 외의 짝수는 소수 아님
        if(num % 2 == 0) return false;
        // 홀수 만 검사 
        int sqrt = (int)Math.Sqrt(num);        
        for(int i = 3; i < sqrt; i+=2)
        {
            if(num % i == 0) return false;
        }
        return true;
    }
}

느낀 점

아직 부족함을 느낍니다..