[Lv2] 소수 찾기

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

문제 설명

 

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers	return
"17"	3
"011"	2

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

문제 원출처: http://2009.nwerc.eu/results/nwerc09.pdf

 

---

 

소수는 이미 에라토스테네스의 체를 활용한 방법으로 다루었으니 아래를 참고.

[Coding Quiz/programmers] - [Lv1] 소수의 합, 소수 찾기

 

문자열로 된 수에서 1~n자의 길이로 된 숫자를 만드는 법을 봅시다.

char[] nums = numbers.toCharArray();
boolean[] check = new boolean[nums.length];
results = new TreeSet<>();
makenum(nums, check, "");

주어지는 문자열 numbers로 char 배열을 만들고, boolean 배열로 사용된 여부를 알도록 같이 생성.

 

중복이 없고 오른차순으로 정렬되는 TreeSet을 전역변수로 생성.

 

makenum이라는 재귀함수를 호출.

public void makenum(char[] nums, boolean[] check, String now) {
    int startindex = -1;
    for(int i=0;i<check.length;i++) {
        if(!check[i]) {
            startindex = i;
            break;
        }
    }
    if(startindex==-1) return;
    else {
        for(int i=startindex;i<nums.length;i++) {
            if(!check[i] && (nums[i]!='0'||now.length()!=0)) {
                boolean[] newcheck = check.clone();
                newcheck[i] = true;
                results.add(Integer.parseInt(now+nums[i]));
                makenum(nums, newcheck, now+nums[i]);
            }
        }
    }
}

boolean 배열로 사용여부를 보고, 모두 이미 사용했다면 return,

 

그렇지 않으면 사용하지 않은 숫자를 쓰면서(newcheck로 새로운 사용여부 넣어서)

 

TreeSet에 추가(중복이면 자동으로 무시됨.), 재귀함수로 사용하여 모든 경우에 대해 탐색.

 

만들어진 문자열 now가 없는데 처음에 0은 못들어가도록 조건 설정.

 

다시 makenum 함수 이후로 오면,

if(results.contains(1)) results.remove(Integer.valueOf(1));
int max = results.last();
int calmax = (int)(Math.sqrt(max));
for(int i=2;i<=calmax;i++) {
    for(int j=i*2;j<=max;j+=i) {
        if(results.contains(j)) results.remove(Integer.valueOf(j));
    }
}
return results.size();

TreeSet에서 1은 어차피 소수가 될 수 없으니 제거.

 

이제 에라토스테네스의 체로, TreeSet에 생성된 수 중 가장 큰 수를 빼와서 루트값으로 계산최댓값을 구함.

 

에라토스테네스의 체로, TreeSet에 값이 있으면 제거함.

 

마지막으로 TreeSet에 생존한 수는 소수들임.

 

 

이대로 실행해보면 속도는 조금 느리게 나옴.

 

makenum 함수 호출시 숫자를 쓸 때마다 그에 대한 boolean 배열을 새로 만들기도 하고,

 

TreeSet을 사용하거나, contains 부분 등.. 메모리나 속도에서 좋은 코드는 아님.

 

하지만 진자 효율성을 볼거면 효율성 점수 부분이 있을테니, Level2는 그냥 거쳐가는 정도로 생각하려고 함..