C# 소수 찾기 - DFS 순열 / 프로그래머스 [Lv.2]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/42839

 

 

나의 풀이

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

public class Solution {
    public int solution(string numbers) 
    {
        var hashSet = new HashSet<int>();
        
        for(int i = 1; i <= numbers.Length; ++i)
            Perm(numbers.ToCharArray(), 0, i, hashSet);
        
        int answer = 0;
        foreach(int num in hashSet)
        {
            if(IsPrimer(num))
                ++answer;
        }
        return answer;
    }
    
    private void Perm(char[] arr, int depth, int length, HashSet<int> hashSet)
    {
        if(depth == length)
        {
            string result = new string(arr.Take(length).ToArray());
            hashSet.Add(int.Parse(result));
            return;
        }
        
        for(int i = depth; i < arr.Length; i++)
        {
            Swap(arr, i, depth);
            Perm(arr, depth + 1, length, hashSet);
            Swap(arr, i, depth);
        }
    }
    
    private static void Swap(char[] arr, int x, int y)
    {
        char temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }
    
    private bool IsPrimer(int n)
    {
        if(n <= 1) return false;
        for(int i = 2; i * i <= n; i++)
        {
            if(n % i == 0)
                return false;
        }
        return true;
    }
}

순열을 만든다음 소수 판별만 해주면 되는 문제.

처음 풀때 실수로 arr를 Clone()해서 넘겼는데, Perm 함수를 빠져나올 때 다시 원래대로 돌리는 부분이 있으니 복사안해도된다. 괜히 공간복잡도는 커질듯.

 

 

 

다른사람 풀이

using System;
using System.Collections.Generic;
using System.Data;

public class Solution
{
    public int solution(string numbers)
    {
        HashSet<int> primeNumbers = new HashSet<int>();

        for (int index = 0; index < numbers.Length; ++index)
        {
            string[] tempNum = CombineString(index, numbers);
            for (int tempNumIndex = 0; tempNumIndex < tempNum.Length; ++tempNumIndex)
            {
                int tempPrime = int.Parse(tempNum[tempNumIndex]);
                if (isPrime(tempPrime))
                    primeNumbers.Add(tempPrime);
            }
        }


        return primeNumbers.Count;
    }

    string[] CombineString(int ciphers, string numbers)
    {
        List<string> numberList = new List<string>();
        List<char> charList = new List<char>(numbers.ToCharArray());
        char[] newString = new char[ciphers+2];
        for( int charIndex = charList.Count-1;  charIndex >= 0 ; --charIndex)
            CreateStringNum(ciphers, charIndex, ref numberList, charList, newString);
        return numberList.ToArray();
    }

    void CreateStringNum(int ciphers, int charIndex, ref List<string> numberList, List<char> charList, char[] newString)
    {
        if (ciphers < 0)
        {
            numberList.Add(new string(newString));
            return;
        }

        if (charIndex < 0)
            return;

        CreateStringNum(ciphers, charIndex - 1, ref numberList, new List<char>( charList ), newString);

        newString[ciphers] = charList[charIndex];
        charList.RemoveAt(charIndex);

        CreateStringNum(ciphers - 1, charList.Count - 1, ref numberList, new List<char>(charList), newString);
    }

    bool isPrime(int num)
    {
        if (num == 2)
            return true;

        if (num < 2 || (num & 1) == 0)
            return false;

        for(int div = 3; div <= Math.Sqrt( num ); div += 2)
        {
            if (num % div == 0)
                return false;
        }

        return true;
    }
}