Programmers Level2 소수찾기 with Java and Python

안녕하세요.

 

이번에는 Project Euler에 이어서 Programmers 문제를 가져왔습니다 !

 

이번에도 마찬가지로 기본적인 알고리즘 코딩이 많이 부족하다고 생각하여 효율이 떨어지더라도 우선 문제를 풀어보는거에 중점을 두고,

필요 API등만 검색해보고 직접 풀어보는 형식으로 진행 하였습니다.

* 아마 문제를 검색해보시면 풀이 방법들이 많이 잘 나와 있을거에요. (위에서 언급한대로 문제 자체를 검색하지 않았다는 점 말씀드립니다.)

 

이번에도 소스코드에 대한 설명은 없이 기록용이므로 바로 풀이를 하도록 하겠습니다.

* 문제 풀이는 Java, Python 2버전, Python 3 버전을 사용하여 진행 하였습니다.

 

Programmers의 문제는 한글로 되어있고, 금방 찾아 보실 수 있으니 문제 내용은 생략 하도록 하겠습니다.

 

1. Solved with Java

import java.lang.Math;
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
 
class Solution {
    public int solution(String numbers) {
        int num=numbers.length();
        List<String> checkDuplicate = new ArrayList<String>();
        LinkedList<Integer> perArr = new LinkedList<Integer>();
        List<String> initList = Arrays.asList(numbers.split(""));
        int[] perCheck = new int[num];
        
        for(int i=1; i<num+1; i++){
            permutation(num, i, perArr, perCheck, initList, checkDuplicate);
        }
        return checkPrimeNum(checkDuplicate);
    }
    
    private static int checkPrimeNum(List<String> checkList){
        List<Integer> convertList = new ArrayList<Integer>();
        List<Integer> primeNum = new ArrayList<Integer>();
        
        for(String el:checkList){
            int convertVal = Integer.parseInt(el, 10);
            if(!convertList.contains(convertVal) 
              && convertVal!=0 && convertVal!=1){
                convertList.add(convertVal);
            }
        }
        
        for(int el: convertList){
            int count=0;
            double elSqrt = Math.sqrt(el);
            double checkZero = elSqrt - (int)elSqrt;
            if(checkZero!=0.0){
                //for(int i=1; i<el+1; i++){
                for(int i=1; i<(int)elSqrt+1; i++){
                    if(el%i==0){
                        count++;
                    }
                }
                count++;
                if(count==2){
                    primeNum.add(el);
                }
            }
        }
        return primeNum.size();
    }
    
    private static void permutation(int n, int r, LinkedList<Integer> perArr,
                                   int[] perCheck, List<String> initList,
                                   List<String> checkDuplicate){
        String checkStr = "";
        if(perArr.size()==r){
            for(int el: perArr){
                checkStr+=el;
                if(!checkDuplicate.contains(checkStr)){
                    checkDuplicate.add(checkStr);
                }
            }
            return;
        }
        
        for(int i=0; i<n; i++){
            if(perCheck[i]==0){
                perArr.add(Integer.parseInt(initList.get(i), 10));
                perCheck[i]=1;
                permutation(n, r, perArr, perCheck, initList, checkDuplicate);
                perCheck[i]=0;
                perArr.removeLast();
            }
        }
    }
}

 

 

2. Solved with Python 2, Python 3

from itertools import permutations
from math import sqrt
 
def solution(numbers):
    return primeNum(numbers)
 
def primeNum(number):
    items = list(number)
    itemLen = len(items)+1
    setDuplicate = []
    
    for i in range(1, itemLen):
        check = set(permutations(items, i))
        for j in check:
            strs = ""
            for k in j:
                strs += k
            num = int(strs, 10)
            if num==0 or num==1:
                pass
            else:
                if num not in setDuplicate:
                    if primeCheck(num):
                        setDuplicate.append(num)
                    else:
                        pass
                else:
                    pass
    
    return len(setDuplicate)
 
def primeCheck(num):
    numSqrt = sqrt(num)
    checkSqrt = int(numSqrt)+1
    checkZero = numSqrt - int(numSqrt)
    count = 0
    if sqrtCheck(checkZero):
        for i in range(1, checkSqrt):
            if(num%i==0):
                count+=1
            else:
                pass
        count+=1
        if count==2:
            return True
        else:
            return False
    else:
        return False
 
def sqrtCheck(checkZero):
    if checkZero!=0.0:
        return True
    else:
        return False

 

결과는 직접 확인해 보세요 ~!