[프로그래머스 C#] 완전탐색 > 소수찾기

문제 

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

프로그래머스

문제 설명

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

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

제한사항

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

풀이 

숫자조합을 만들지 못해서 여기저기 블로그를 참고해서 코드를 완성했다.

011인 경우 

0이 1개 

1이 2개 이다. 

첫번째 자리수가 1 일 때 다음으로 올 수 있는 수는 1 또는 0이다. 

두번째 자리수가 1일때 다음에 올수 있는건 0이다. 

두번째 자리수가 0일떄 다음에 올 수 있는건 1이다. 

 

우리는 위의 글처럼 생각하고 문제를 해결할것이다. 

따라서 num 배열에 0~9까지 숫자카드가 몇개 있는지 저장할것이다. 

나머지 설명은 주석을 참고하자. 

using System;
using System.Collections.Generic;

public class Solution {
    int[] num = new int[10]; // 0~9까지 숫자가 몇개 있는지 세는 배열num
    Stack<int> stk = new Stack<int>();
    
    public int solution(string numbers) {
    //    int answer = 0;
        int len = numbers.Length;
        for(int i=0; i<numbers.Length; i++)
        {
            //아스키 문자가 0~127사이의 앖으로 표현됨 문자 '0'에서 
            // 해당하는 정수를 얻으려면 간단히 '0'을 빼면됨
            num[numbers[i]-'0']++;
        }
        for(int i=1; i<=len; i++)
        {
            per(num,i,0,0); //깊이는 1부터 
        }
        
        return stk.Count;
    }
    //소수판별
    
   public bool isPrime(int n)
    {
        if(n== 2)
            return true;
        if(n <= 1 || n%2==0)
            return false;
        for(int i = 3; i<=Math.Sqrt((float)n);i+=2)
            if(n%i==0)
                return false;
        return true;
    }
    
    
    //숫자 조합 만들기
    //arr 숫자 배열 des 깊이 n 총 배열안에 들어있는 숫자 sum 몇개를 뽑아서 순열을 만들것인지
    //arr에는 0부터 9까지 숫자가 몇개있는지 들어있음
    public void per(int[] arr, int des, int n, int sum)
    {
        //des가 n에 도달하면 사이클이 돌았으니 
        if (des == n && isPrime(sum)) //깊이가 n과 같고 소수면
        {
            if(!stk.Contains(sum)) //스택에 없으면 push
            {
                stk.Push(sum);
            }
        }
        else
        {
            for(int i=0; i<10; i++)
            {
                if(arr[i]>0)
                {
                    arr[i]--; //사용했으니까 줄임
                    int ten =1;
                    for(int j=0; j<des-n-1; j++)
                    {
                        ten*=10;
                    }
                    per(arr,des,n+1,sum+(i*ten));
                    arr[i]++; //다 썼으니까 다시 올림
                }
            }
        }
    }   
}