[C#] 소수 찾기 (완전 탐색)

프로그래머스 문제

문제 설명

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

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

제한사항

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

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

자력으로 푸는데 실패한 관계로 다른 분 코드 퍼옴

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(string numbers)
    {
        int nAnswer = 0;
        int nResult = 0;
        int nMod = 0;
        int nMax = 0;
        List<int> lstNumber = new List<int>(numbers.Length);
        
        foreach (var vCh in numbers.ToCharArray())
        {
            lstNumber.Add(vCh - 0x30);
        }
        lstNumber.Sort();

        for (int i = lstNumber.Count - 1; i >= 0; --i)
        {
            nMax += (lstNumber[i] * (int)Math.Pow(10, i));
        }
        
        List<bool> lstPrimes = new List<bool>(GetPrimes(nMax));
        List<int> lstPrimeDigit = new List<int>();

        for (int k = 2; k < lstPrimes.Count; ++k)
        {
            if (lstPrimes[k] == false)
                continue;

            bool bIncludeNumber = true;
            bool bIncludeDigit = false;
            nResult = k;

            lstPrimeDigit.Clear();
            do
            {
                nMod = nResult % 10;
                nResult /= 10;

                lstPrimeDigit.Add(nMod);
            } 
            while (nResult > 0);
            
            List<int> lstNumberTempo = new List<int>(lstNumber);

            for (int i = 0; i < lstPrimeDigit.Count; ++i)
            {
                bIncludeDigit = false;
                
                for (int j = 0; j < lstNumberTempo.Count; ++j)
                {
                    if (lstPrimeDigit[i] == lstNumberTempo[j])
                    {
                        bIncludeDigit = true;
                        lstNumberTempo[j] = -1;
                        break;
                    }
                }

                bIncludeNumber &= bIncludeDigit;
                if (!bIncludeNumber)
                {
                    break;
                }
            }

            if (bIncludeNumber)
                ++nAnswer;
        }

        return nAnswer;
    }

    bool[] GetPrimes(int nMax)
    {
        List<bool> lstPrimes = new List<bool>(nMax);

        for (int i = 0; i <= nMax; ++i)
            lstPrimes.Add(true);

        for (int i = 2; i <= nMax; ++i)
        {
            for (int j = i * 2; j <= nMax; j += i)
                lstPrimes[j] = false;
        }

        return lstPrimes.ToArray();
    }
}

느낀 점: 아직도 머리 속으로는 어떻게 푸는지 알겠는데 그걸 코드로 정리하여 풀어쓰는 능력이 부족한 것을 절실하게 느낀 문제이다.

 

사실 다른 분의 코드를 보고 이해는 할 수 있지만 다시 풀라고 하여도 풀기 힘들 것 같다. 

 

그러니 내가 생각은 하였지만 코드로 풀어내지 못하였던 부분만 정리를 하고 넘어가겟다.

 

for (int i = lstNumber.Count - 1; i >= 0; --i)
{
    nMax += (lstNumber[i] * (int)Math.Pow(10, i));
 }

-리스트의 각자리수에 십의 i승을 곱하는 반복문을 돌려주어 모든 자릿수 일때의 경우의 수 도출.

 

foreach (var vCh in numbers.ToCharArray())
{
   lstNumber.Add(vCh - 0x30);
}

 - 해당 char형 배열의 값의 아스키코드 값으 빼주어 숫자 값으로 리스트에 Add