104. 소수 찾기(재귀 함수를 이용한 소수 만들기)

 

문제를 보고 소수를 만들 방법에 대해 많은 고민을 했다.

 

재귀함수를 사용해서 소수를 만들어야 하는 상황이라 

 

매개변수로 무슨 값을 줘야할지 많이 고민했다.

 

고민 끝에 나온 결론으로는 

 

1. 제한 시킬 글자 수

2. 현재 만들어진 숫자(문자열)

3. numbers(제공 될 문자열)

 

로 선택했다.

 

재귀함수의 반환형은 void로 설정 했는데 이유는 딱히 반환해야 할 내용이 없어 보였기 때문이다.

 

    // 필요한 매개변수
    // 제한 시킬 글자 수
    // 현재 만들어진 숫자(문자열)
    // numbers(제공 될 문자열)
    public void MakeNumber(int length, string currentWords, string numbers) {
        
        if(currentWords.Length == length + 1) return;
        
    }

 

먼저 현재 만들어진 문자열의 길이가 제한된 문자열의 길이 보다 1 클 경우 함수를 종료하도록 만들었다.

 

(

 

처음에는 현재 만들어진 문자열의 길이가 제한된 길이와 같으면 종료로 설정했는데 그럴 경우

제한된 사이즈 만큼 완성된 문자열을 hashSet에 저장하지 못 하는 문제가 존재했다.

 

)

 

    // 필요한 매개변수
    // 제한 시킬 글자 수
    // 현재 만들어진 숫자(문자열)
    // numbers(제공 될 문자열)
    public void MakeNumber(int length, string currentWords, string numbers) {
        
        if(currentWords.Length == length + 1) return;
        
        int.TryParse(currentWords, out int result);
        if(result != 0 && result != 1) hashSet.Add(result);
        
 	}

 

그 후, 현재 만들어진 숫자(string 타입)이 int.Parse이 아니라 int.TryParse을

 

사용해 "" 같은 공백 오류를 제거한 int형 정수 중 0과 1을 제외하고 hashSet에 저장해줬다.

(공백은 0으로 변환된다)

 

    // 필요한 매개변수
    // 제한 시킬 글자 수
    // 현재 만들어진 숫자(문자열)
    // numbers(제공 될 문자열)
    public void MakeNumber(int length, string currentWords, string numbers) {
        
        if(currentWords.Length == length + 1) return;
        
        int.TryParse(currentWords, out int result);
        if(result != 0 && result != 1) hashSet.Add(result);
        
        for(int i = 0; i < numbers.Length; i++)
        {
            MakeNumber(length, currentWords + numbers[i], numbers.Remove(i, 1));
        }
    }

 

마지막으로 for과 재귀함수를 사용해 추가할 숫자를 지정한 후 numbers.Remove(i,1)로 사용된 숫자는 제거해줬다.

 

( Remove(i, 1) 중요!! 안 쓰면 사용된 숫자가 다시 사용되는 현상이 발생 합니다!)

 

이렇게 만들어진 hashSet의 요소들을 

 

    public int IsPrime(int number)
    {
        bool check = true;
        for(int i = 2; i <= (int)Math.Sqrt(number); i++)
        {
            if(number % i == 0) check = false;
        }
        return check ? 1 : 0;
    }

 

소수를 판별하는 함수에 집어 넣고 소수이면 1, 아니면 0을 반환시켜준다.

 

    public int solution(string numbers) {
        int answer = 0;
        
        MakeNumber(numbers.Length, "",numbers);
        
        foreach(int element in hashSet)
        {
            answer += IsPrime(element);
        }
        
        return answer;
    }

 

반환 받은 숫자를 answer에 추가 할 수 있게 만들어 결과를 도출하면 된다.

 

전체 코드 :

 

using System;
using System.Collections.Generic;

public class Solution {

    public HashSet<int> hashSet = new HashSet<int>();
    
    // 필요한 매개변수
    // 제한 시킬 글자 수
    // 현재 만들어진 숫자(문자열)
    // numbers(제공 될 문자열)
    public void MakeNumber(int length, string currentWords, string numbers) {
        
        if(currentWords.Length == length + 1) return;
        
        int.TryParse(currentWords, out int result);
        if(result != 0 && result != 1) hashSet.Add(result);
        
        for(int i = 0; i < numbers.Length; i++)
        {
            MakeNumber(length, currentWords + numbers[i], numbers.Remove(i, 1));
        }
    }
    
    public int IsPrime(int number)
    {
        bool check = true;
        for(int i = 2; i <= (int)Math.Sqrt(number); i++)
        {
            if(number % i == 0) check = false;
        }
        return check ? 1 : 0;
    }
    
    public int solution(string numbers) {
        int answer = 0;
        
        MakeNumber(numbers.Length, "",numbers);
        
        foreach(int element in hashSet)
        {
            answer += IsPrime(element);
        }
        
        return answer;
    }
}