[코딩테스트] 소수 찾기

문제

---

소수 찾기 문제 바로가기

제출 코드(JAVA)

---

첫번째 코드 제출

import java.util.*;

class Solution {
    Set<Integer> primeSet  = new HashSet<>();;
    char[] chars;
    int result = 0;

   public int solution(String numbers) {
        chars = numbers.toCharArray();

        for (int i = 0; i < chars.length; i++) {
            char[] array = new char[i+1];
            int[] check = new int[chars.length];
            permutation(array, 0, check);
        }

        Iterator<Integer> iter = primeSet.iterator();

        while (iter.hasNext()) {
            if (isPrime(iter.next())) { result++; }
        }

        return result;
    }

    private void permutation(char[] array, int depth, int[] check) {
            for (int i = 0; i < chars.length; i++) {
                if (check[i] == 1) { continue; }
                array[depth] = chars[i];
                if (isLastPermutation(array, depth)) {
                    addPrime(array);
                } else {
                    check[i] = 1;
                    permutation(array, depth+1, check);
                    check[i] = 0;
            }
        }
    }
    
    private void addPrime(char[] array){
        Integer prime = mapToInteger(array);
        primeSet.add(prime);
    }
    
    private boolean isLastPermutation(char[] array, int depth) {
        return depth == array.length-1;
    }

    private Integer mapToInteger(char[] array) {
        StringBuffer sb = new StringBuffer();
        for (char c : array) {
            sb.append(c);
        }
        return Integer.valueOf(sb.toString());
    }

    public boolean isPrime(int num){
        if (num < 2) { return false; }
        for(int i=2; i*i<=num; i++){
            if(num % i == 0) return false;
        }
        System.out.println(num);
        return true;
    }
}

재귀 사용하여 탐색을 진행했고, Set을 사용해 중복을 제거했다

정확성 테스트

정확성  테스트
테스트 1 〉	통과 (0.76ms, 52.4MB)
테스트 2 〉	통과 (11.18ms, 53.9MB)
테스트 3 〉	통과 (0.36ms, 52.5MB)
테스트 4 〉	통과 (5.89ms, 53.4MB)
테스트 5 〉	통과 (10.12ms, 66MB)
테스트 6 〉	통과 (0.36ms, 52.3MB)
테스트 7 〉	통과 (1.07ms, 52.2MB)
테스트 8 〉	통과 (23.52ms, 58.1MB)
테스트 9 〉	통과 (0.44ms, 52.6MB)
테스트 10 〉	통과 (17.00ms, 53.5MB)
테스트 11 〉	통과 (3.28ms, 53.2MB)
테스트 12 〉	통과 (2.12ms, 53.1MB)

두번째 코드 제출

public int solution(String numbers) {
        HashSet<Integer> set = new HashSet<>();
        permutation("", numbers, set);
        int count = 0;
        while(set.iterator().hasNext()){
            int a = set.iterator().next();
            set.remove(a);
            if(a==2) count++;
            if(a%2!=0 && isPrime(a)){
                count++;
            }
        }
        return count;
    }

    public boolean isPrime(int n){
        if(n==0 || n==1) return false;
        for(int i=3; i<=(int)Math.sqrt(n); i+=2){
            if(n%i==0) return false;
        }
        return true;
    }

    public void permutation(String prefix, String str, HashSet<Integer> set) {
        int n = str.length();
        //if (n == 0) System.out.println(prefix);
        if(!prefix.equals("")) set.add(Integer.valueOf(prefix));
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), set);
    }

풀었던 방식과 비슷하지만 재귀하는 방식에서 약간 다른 차이를 보였다.

정확성 테스트

정확성  테스트
테스트 1 〉	통과 (13.07ms, 54.1MB)
테스트 2 〉	통과 (59.13ms, 54.5MB)
테스트 3 〉	통과 (15.41ms, 53.3MB)
테스트 4 〉	통과 (28.39ms, 55MB)
테스트 5 〉	통과 (54.34ms, 55.9MB)
테스트 6 〉	통과 (18.39ms, 52.6MB)
테스트 7 〉	통과 (23.95ms, 53.2MB)
테스트 8 〉	통과 (46.36ms, 55.7MB)
테스트 9 〉	통과 (21.16ms, 53.3MB)
테스트 10 〉	통과 (66.40ms, 54.3MB)
테스트 11 〉	통과 (18.89ms, 53.4MB)
테스트 12 〉	통과 (16.45ms, 53.4MB)

저 재귀함수 스타일을 많이 사용하는 것 같으나 String타입에 대한 무분별한 substring으로 속도적인 측면에서 많이 저하되는 것 같다

제출 코드(Python)

---

코드 제출

import math

def permutation(idxArray, depth, array, strArry, primeSet):
    for i in range(len(strArry)):
        if idxArray[i] == 1:
            continue
        array[depth] = strArry[i]
        if depth == len(array) - 1:
            num = ''
            for n in array:
                num += n
            primeSet.add(int(num))
        else:
            idxArray[i] = 1
            permutation(idxArray, depth + 1, array, strArry, primeSet)
            idxArray[i] = 0


def is_prime_number(x):
    if x < 2 or (x != 2 and x % 2 == 0):
        return False
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True


def solution(numbers):
    primeSet = set()
    strArry = [*numbers]
    result = 0

    for i in range(len(numbers)):
        idx = [0 for n in range(len(numbers))]
        array = [0 for n in range(i + 1)]
        permutation(idx, 0, array, strArry, primeSet)

    for v in primeSet:
        if is_prime_number(v):
            print(v)
            result += 1

    return result

java 제출풀이와 같은 방식의 풀이

정확성 테스트

정확성  테스트
테스트 1 〉	통과 (0.16ms, 10.4MB)
테스트 2 〉	통과 (4.76ms, 10.4MB)
테스트 3 〉	통과 (0.05ms, 10.5MB)
테스트 4 〉	통과 (2.79ms, 10.4MB)
테스트 5 〉	통과 (16.69ms, 10.4MB)
테스트 6 〉	통과 (0.05ms, 10.5MB)
테스트 7 〉	통과 (0.18ms, 10.4MB)
테스트 8 〉	통과 (16.76ms, 10.5MB)
테스트 9 〉	통과 (0.08ms, 10.4MB)
테스트 10 〉	통과 (7.44ms, 10.4MB)
테스트 11 〉	통과 (1.19ms, 10.4MB)
테스트 12 〉	통과 (0.85ms, 10.4MB)