[프로그래머스 C#] Lv.2 소수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

- '만들 수 있는' 모든 소수의 개수를 구하는 것이기 때문에 DFS를 떠올렸다면 해결 가능!

- 주의할 부분은 매개변수로 넘긴 방문체크배열은 참조하여 사용하기 때문에, 사용이 끝나면 방문상태를 다시 변경해줘야 함

https://godgjwnsgur7.tistory.com/47

[C#] DFS(Depth First Search), BFS(Breadth First Search)

+ 소수 체크 범위는 그냥 num - 1 또는 num / 2 로 해도 통과가 안되진 않겠지만, Sqrt를 사용하자. 빠르다.

    using System;
    using System.Collections.Generic;

    public class Solution
    {
        public List<int> list = new List<int>(); // 소수리스트

        public int solution(string numbers)
        {
            int answer = 0;
            bool[] boolArray = new bool[numbers.Length]; 
            char[] charArray = new char[numbers.Length]; 

            for (int i = 0; i < numbers.Length; i++)
            {
                boolArray[i] = false; // 방문 배열
                charArray[i] = numbers[i]; // 숫자 조각
            }

            DFS(boolArray, charArray, new string(""));

            foreach (int num in list)
                if (IsCheck(num))
                    answer++;

            return answer;
        }
        
        // 재귀 대상 DFS 함수
        public void DFS(bool[] boolArray, char[] charArray, string str)
        {
            if (str.Length == boolArray.Length)
                return;

            for (int i = 0; i < boolArray.Length; i++)
            {
                if (boolArray[i])
                    continue;

                boolArray[i] = true;
                DFS(boolArray, charArray, str + charArray[i]);
                boolArray[i] = false; // 참조하여 사용하기 때문에 해제 필수!

                int tempNum = Int32.Parse(str + charArray[i]);
                if (!list.Contains(tempNum))
                    list.Add(tempNum); // 소수 리스트에 추가
            }
        }

        // 소수 체크 함수
        public bool IsCheck(int num)
        {
            if (num <= 1)
                return false;

            for (int i = 2; i <= Math.Sqrt(num); i++)
                if (num % i == 0)
                    return false;

            return true;
        }
    }