프로그래머스 소수 찾기 (C#) [Lv. 2]

프로그래머스

 

수를 strinf으로 입력 받을 때, 해당 수들을 조합해서 만들 수 있는 수 중에 소수인 것들의 개수를 구해주세요. (중복 조합 x)

 

풀이 방법

해당 문제는 2개로 구분하여 풀이합니다. 

1. 중복 없이 조합하기

2. 소수인지 체크하기

 

우선 중복 없이 조합하는 방법을 소개하겠습니다.

중복 없이 조합하는 방법

public void DFS(string str = "")
{
    for (int i = 0; i < Numbers.Length; i++)
    {
    	...
        ...
        DFS(str + numbers[i]);
    }
}

 

DFS와 반복문을 조합하여 수를 조합합니다.

 

public void DFS(bool[] visited, string str = "")
{
    for (int i = 0; i < Numbers.Length; i++)
    {
    	if (visited[i]) continue;
        visited[i] = true;
    	...
        ...
        DFS(visited, str + numbers[i]);
        visited[i] = false;
    }
}

이 때, 수를 중복하여 사용할 수는 없기 때문에 방문 배열을 사용합니다.

이미 방문한 인덱스라면 건너뛰어주고 방문 배열에 체크합니다.

이후, 다음 사용을 위해 false로 초기화 해줍니다.

 

 

소수인지 체크하기

소수는 나뉘는 수가 1과 자기 자신인 수를 의미합니다.

즉 반복문을 통해 나뉘는 수가 있는지 체크해줍니다.

for (int i = 2; i < n; i++)
{
	if (n % i == 0)
    	return false;
}

return true;

 

이렇게만 해줘도 해당 문제는 해결이 가능합니다.

다만, N번씩 체크를 해줘야한다는 것이 성능적으로 많이 아쉽습니다.

시간과 관련해서 빡빡한 문제였다면 시간초과가 뜰 수 밖에 없는 로직입니다.

 

빠른 속도로 소수 체크하기

소수를 체크하는 부분은 N까지 할 필요 없이 N의 제곱근까지만 해줘도 찾을 수 있습니다.

즉, 

for (int i = 0; i < n; i++)

이 아니라

 

for (int i = 2; i * i <= n; i++)

로 해도 정확하게 같은 답을 구할 수가 있습니다.

 

N이 10000인 상황이라고 하면, 만번 계산하는 것이 아니라 100번만 계산하므로, 속도 측면에서 굉장히 유리합니다.

 

 

정답 코드

using System;
using System.Collections.Generic;

public class Solution 
{
    HashSet<int> trys = new HashSet<int>();
    
    string Numbers;
    int answer = 0;
    
    public void IsPrimeNum(int num)
    {
        if (trys.Contains(num) || num < 2)
            return;
        
        trys.Add(num);
        
        bool flag = true;
        for (int i = 2; i * i <= num; i++)
        {
            if (num % i == 0)
            {
                flag = false;
                break;
            }
        }
        
        if (flag) answer++;
    }
    
    
    public void DFS(bool[] visited, string str = "")
    {
        if (int.TryParse(str, out int ret))
            IsPrimeNum(ret);
        
        for (int i = 0; i < Numbers.Length; i++)
        {
            if (visited[i]) continue;
            
            visited[i] = true;
            DFS(visited, str + Numbers[i]);
            visited[i] = false;
        }
    }
    
    public int solution(string numbers) 
    {
        Numbers = numbers;
        bool[] visited = new bool[numbers.Length];
        
        DFS(visited);
        return answer;
    }
}