문제

Programmers, 소수 찾기

핵심

• 입력의 크기가 7이라 구현에 초점을 맞춘다.
• 한 자리 숫자가 적힌 종이 조각이 흩어져 있고 이를 마음대로 붙여 가능한 소수 개수를 구해야 한다. 종이 조각이 7개 있다면, 7개 중에서 1개를 고를 수 있고, 2개를 고를 수 있고... 7개를 고를 수 있는 조합 문제이다. 코드로 간략히 다음과 같이 나타낼 수 있다.

for (int i = 1; i <= n; ++i)
	dfs(0, i);

dfs(int depth, int mx) {
	if (depth == mx) {
    	// mx만큼 숫자를 골랐을 때
	}
}

• 이렇게 모든 경우를 구할 수 있지만 두 가지 문제가 생긴다. 이미 어떤 수를 골랐다면 다음에 고를 때 해당 수를 고르지 않기 위해 선택되었음을 표시할 배열을 사용해야 한다. 둘째로 종이 조각이 [0, 3, 3]일 때 가능한 소수는 3 하나지만 조합의 경우 2번째 3과 3번째 3을 다르게 보기 때문에 두 개로 보는 것이다. 중복을 제거할 수 있게 이미 찾은 소수는 해시 자료구조에 저장한다. 만약 어떤 수가 소수일 때 이미 해시 자료구조에 저장되어 있다면 중복된 수로 판단한다.

개선

bool isPrime(int num) {
    if (num < 2)
        return false;
    for (int i = 2; i <= num / i; ++i) {
        if (num % i == 0)
            return false;
    }
    return true;
}

• 위의 코드는 가장 간단하게 소수 찾기 알고리즘을 구현한 것이다.
• 먼저 짝수를 걸러내고 홀수만 찾아내는 식으로 개선할 수 있으며 더 큰 범위에 있는 소수들을 찾는다면 아리토스테네스의 체를 이용해 더 효율적으로 소수를 찾을 수 있다. 다만, 문제를 해결하기 위해 더 개선할 필요는 없었다.

코드

시간복잡도

• $O(n \times nCr \times \sqrt{num})$

C++

#include <string>
#include <vector>
#include <iostream>
#include <unordered_set>

using namespace std;
int ans = 0;
vector<int> nums;
unordered_set<int> primes;
bool isPrime(int num) {
    if (num < 2)
        return false;
    for (int i = 2; i <= num / i; ++i) {
        if (num % i == 0)
            return false;
    }
    return true;
}

void dfs(int depth, int mx, vector<int>& seq, vector<bool>& isVisited) {
    if (depth == mx) {
        int ret = 0;
        for (auto e : seq)
            ret = ret * 10 + e;
        if (primes.find(ret) == primes.end() && isPrime(ret)) {
            ++ans;
            primes.insert(ret);
        }
        return ;
    }
    for (int i = 0; i < nums.size(); ++i) {
        if (isVisited[i])
            continue;
        seq.push_back(nums[i]);
        isVisited[i] = true;
        dfs(depth + 1, mx, seq, isVisited);
        seq.pop_back();
        isVisited[i] = false;
    }
}

int solution(string numbers) {
    for (int i = 0; i < numbers.length(); ++i)
        nums.push_back(numbers[i] - '0');
    for (int i = 0; i < numbers.length(); ++i) {
        vector<bool> isVisited(10, false);
        vector<int> seq;
        dfs(0, i + 1, seq, isVisited);
    }
    return ans;
}

Java

import java.util.*;

class Solution {
    private int ans = 0 ;
    private ArrayList<Integer> nums = new ArrayList<>();
    private Set<Integer> primes = new HashSet<>();
    private boolean isPrime(int num) {
        if (num < 2)
            return false;
        for (int i = 2; i <= num / i; ++i) {
            if (num % i == 0)
                return false;
        }
        return true;
    }
    
    private void dfs(int depth, int mx, ArrayList<Integer> seq, boolean[] isVisited) {
        if (depth == mx) {
            int ret = 0;
            for (int e : seq)
                ret = ret * 10 + e;
            if (!primes.contains(ret) && isPrime(ret)) {
                ++ans;
                primes.add(ret);
            }
            return;
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (isVisited[i])
                continue;
            seq.add(nums.get(i));
            isVisited[i] = true;
            dfs(depth + 1, mx, seq, isVisited);
            seq.remove(seq.size() - 1);
            isVisited[i] = false;
        }
    }
    public int solution(String numbers) {
        for (int i = 0; i < numbers.length(); ++i)
            nums.add(numbers.charAt(i) - '0');
        for (int i = 0; i < numbers.length(); ++i) {
            boolean[] isVisited = new boolean[10];
            dfs(0, i + 1, new ArrayList<>(), isVisited);
        }
        return ans;
    }
}