문제풀이)프로그래머스)c#) 소수찾기

소수찾기

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

코딩테스트 연습 - 소수 찾기

숫자를 조합해서 소수를 찾는 간단한 문제이다. 그러나 막상 경우에 수에 관련된 값을 찾는 과정이 꽤나 걸린다.

1. 주어진 string을 분해해서 트리형 구조로 만들어서 경우에 수를 만든다.

2. 경우에 수에 대한 값을 기준으로 약수에 대한 판별을 해야 한다.

 

첫 번째 약수 판별할 값을 만드는 과정에서 조금 애먹었다. 조금 쉽게 돌아가려고 했지만 결국 트리형 구조로 만들어서 처리를 했다. 원리는 값을 읽어서 현재 값을 제외한 나머지 값을 SubList에 넣는 구조이다. 트리형 구조로 모두 다 값을 넣으면 MakeNumber라는 함수에서 다시 SubList를 반복해서 재귀 호출을 진행한다. SubList가 없으면 넘어간다. 

 

 

코드는 다음과 같다.

public class PrimeNumberInfo{
    public string numbers = "";
    public int value = 0;
    public List<PrimeNumberInfo> subList  =null;
}


 private List<int> m_List  = new List<int>();
    private PrimeNumberInfo root = null;
    private bool PrimeNumber(int _value)
    {
        bool returnValue = true;
        if(_value  < 2){
            return false;        
        }

        for (int i = 2; i < _value; i++)
        {
            
            if (_value % i == 0)
            {
                returnValue = false;
                break;
            }
        }

        return returnValue;
    }
    public void MakeNumber(PrimeNumberInfo _info){
        char[] nums = _info.numbers.ToCharArray();
        for(int i =0;i<nums.Length;i++){
            
            if(null == _info.subList){
                _info.subList = new List<PrimeNumberInfo>();
                
            }

            PrimeNumberInfo info = new PrimeNumberInfo();
            if(_info.value == -1){
                info.value = int.Parse(nums[i].ToString());
            }
            else{
                info.value = int.Parse( _info.value.ToString() + nums[i]);
            }

           

            info.numbers = "";
            for(int j = 0; j < nums.Length;j++){
                if( i == j){
                    continue;
                }
                info.numbers+=nums[j];
            }
            _info.subList.Add(info);

            if(false == this.m_List.Contains(info.value)){
                this.m_List.Add(info.value);
            }
        }

        if(null != _info.subList){
            for(int i =0;i<_info.subList.Count;i++){
                this.MakeNumber(_info.subList[i]);
            }
        }
    }

    public int solution(string numbers)
    {

        //Logger.LogFormat("Solution Value : {0}", numbers);

        int answer = 0;

        char[] nums = numbers.ToCharArray();
        this.m_List = new List<int>();
        root = new PrimeNumberInfo();
        root.numbers = numbers;
        root.value = -1;
        this.MakeNumber(root);

        string debugstring ="";
        for(int i = 0; i< this.m_List.Count;i++){
            int value = this.m_List[i];
            debugstring += value+",";
            if(true == this.PrimeNumber(value)){
                //Logger.LogFormat("PrimeNumber Value :{0}",value);
                answer++;
            }
        }

        //Logger.LogFormat("All Value List :{0}", debugstring);
        //Logger.LogFormat("PrimeNumber Count : {0}",answer);


        return answer;
    }

개인적으로는 코드를 어떻게 편리하게 구성하냐에 고민하는 과정에서 시간이 조금 걸렸다.

PrimeNumber라는 함수에서는 약수를 구분하는 로직이고, MakeNumber에서 값을 만든다.

 

 

 ★★☆☆☆