소수 찾기2
문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다.
흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때,
종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
풀이
public class PrimeNumberGenerator
{
private static List<int> _numbersList = new List<int>();
private static List<int> _primeNumberList = new List<int>();
public static int Solution(string numbers)
{
InitNumbersList(numbers);
int maxNum = _numbersList.Max();
InitPrimeNumberList(maxNum);
return _numbersList.Intersect(_primeNumberList).Count();
}
private static void InitNumbersList(string numbers)
{
//순열을 구성할 숫자 전체 세트를 구성
int[] numberSet = new int [numbers.Length];
for (int i = 0; i < numbers.Length; i++)
{
numberSet[i] = int.Parse(numbers[i].ToString());
}
//이전에 조합에 사용된 숫자를 저장
List<int> prevDigitNumbers = numberSet.ToList();
//전체 자리수에 해당하는 숫자까지 전부 생성하도록 반복
for (int i = 0; i < numbers.Length; i++)
{
//이번에 새로 조합될 숫자를 저장
List<int> currentDigitNumbers = new List<int>();
//이전에 조합된 숫자를 사용
foreach (int number in prevDigitNumbers)
{
//새로운 숫자를 이어붙일 때 현재 이미 사용 중인 숫자를 포함하지 않도록 함
string numStr = number.ToString();
List<int> usingNumbers = numberSet.ToList();
//기존 숫자에서 사용하던 숫자를 제외하고 추가
foreach (char c in numStr)
{
usingNumbers.Remove(int.Parse(c.ToString()));
}
//사용하기로 결정된 숫자만 기존 숫자 뒤에 이어붙힘
foreach (int n in usingNumbers)
{
int tempNum = int.Parse(numStr + n);
//중복되는 숫자는 포함하지 않음
if(!currentDigitNumbers.Contains(tempNum))
currentDigitNumbers.Add(tempNum);
}
}
_numbersList.AddRange(prevDigitNumbers);
prevDigitNumbers = currentDigitNumbers;
}
_numbersList.AddRange(prevDigitNumbers);
}
private static void InitPrimeNumberList(int maxNum)
{
for (var i = 2; i <= maxNum; i++)
{
if(IsPrime(i))
_primeNumberList.Add(i);
}
}
private static bool IsPrime(int number)
{
for (int i = 2; i <= Math.Sqrt(number); i++)
{
if (number % i == 0) return false;
}
return true;
}
}초기 구상
문제 풀이 단계
- 가능한 순열 조합 모두 찾기
- 해당 조합에서 소수 찾기
- 개수를 반환
1. 가능한 순열 조합 모두 찾기
- 가능한 순열 조합을 찾기 위해 고안한 아이디어는 만약 최대 7자리 숫자가 주어진다면 1자리부터 7자리 숫자까지 존재할 수 있음
예시)
12345가 주어진다면
1자리 숫자 :1,2,3,4,5
...
7자리 숫자 :12345,13245... 등의 숫자가 존재해당 과정에서 2자리 숫자로 갈 때
2자리 숫자 :12,13,14,15,21,23...
기존 1자리 숫자에서 해당 숫자에 해당하지 않는 요소 중에 하나를 뒤에 붙이는 과정으로 순열을 구성할 수 있다는 것을 알게됨
private static List<int> _numbersList = new List<int>();- 전체 숫자 순열을 담을 리스트를 생성
private static void InitNumbersList(string numbers)
{
//순열을 구성할 숫자 전체 세트를 구성
int[] numberSet = new int [numbers.Length];
for (int i = 0; i < numbers.Length; i++)
{
numberSet[i] = int.Parse(numbers[i].ToString());
}
//이전에 조합에 사용된 숫자를 저장
List<int> prevDigitNumbers = numberSet.ToList();
//전체 자리수에 해당하는 숫자까지 전부 생성하도록 반복
for (int i = 0; i < numbers.Length; i++)
{
//이번에 새로 조합될 숫자를 저장
List<int> currentDigitNumbers = new List<int>();
//이전에 조합된 숫자를 사용
foreach (int number in prevDigitNumbers)
{
//새로운 숫자를 이어붙일 때 현재 이미 사용 중인 숫자를 포함하지 않도록 함
string numStr = number.ToString();
List<int> usingNumbers = numberSet.ToList();
//기존 숫자에서 사용하던 숫자를 제외하고 추가
foreach (char c in numStr)
{
usingNumbers.Remove(int.Parse(c.ToString()));
}
//사용하기로 결정된 숫자만 기존 숫자 뒤에 이어붙힘
foreach (int n in usingNumbers)
{
int tempNum = int.Parse(numStr + n);
//중복되는 숫자는 포함하지 않음
if(!currentDigitNumbers.Contains(tempNum))
currentDigitNumbers.Add(tempNum);
}
}
_numbersList.AddRange(prevDigitNumbers);
prevDigitNumbers = currentDigitNumbers;
}
_numbersList.AddRange(prevDigitNumbers);
}- 앞서 문제에서 언급된 종이 조각이 될 순열의 재료가 될 숫자들을
numberSet에 저장 prevDigitNumbers에 이전에 사용한 숫자 조합을 넣고 이후 반복문에서 해당 숫자 뒤에 재료가 될 숫자를 선택해서 붙이는 방식으로 새로운 순열을 생성
string numStr = number.ToString();
List<int> usingNumbers = numberSet.ToList();
//기존 숫자에서 사용하던 숫자를 제외하고 추가
foreach (char c in numStr)
{
usingNumbers.Remove(int.Parse(c.ToString()));
}- 뒤에 숫자를 붙이기 전에 이미 사용하던 숫자는 제외하도록 함
- 그렇게 만들어진 숫자 조합을 전체 숫자 리스트인
_numbersList에 추가
2. 해당 조합에서 소수 찾기
- 소수를 찾기위해 만들 수 있는 숫자 중 가장 큰 숫자를 기준으로 범위 내에 존재하는 소수를 미리 찾아 전체 숫자 리스트와 비교
private static void InitPrimeNumberList(int maxNum)
{
for (var i = 2; i <= maxNum; i++)
{
if(IsPrime(i))
_primeNumberList.Add(i);
}
}
private static bool IsPrime(int number)
{
for (int i = 2; i <= Math.Sqrt(number); i++)
{
if (number % i == 0) return false;
}
return true;
}- 소수 찾기 문제에서 학습한 점을 응용하여 소수를 찾을 때에는 에라토스테네스의 체에서 사용한 원리로 해당 숫자의 소수 여부를 판단할 때 숫자의 제곱근 범위에서 배수인지 확인하여 해당 숫자의 소수 여부를 판단해 소수 목록인
_primeNumberList를 작성
3. 소수의 개수를 반환
return _numbersList.Intersect(_primeNumberList).Count();- 전체 숫자와 소수 목록에서 겹치는 숫자 리스트의 길이를 반환하여 문제를 해결
- 다만 이전에 최대 값을 기준으로 소수 목록을 작성하였는데
_numbersList의 각각의 값이 소수인지 판단하는 것이 무조건 최대값 이하의 전체 숫자에서 소수를 찾는 검사보다 검사량이 적으므로 현재 방법보다는_numbersList의 각 성분을 검사하며 소수인지 판단하는 것이 유리할 것으로 보임
