[JAVA ]프로그래머스 - 소수 찾기(findPrimeNumbers) 42839
문제 : https://programmers.co.kr/learn/courses/30/lessons/42839
public class Solution {
public int solution(String numbers) {
int answer = 0;
List numList = new ArrayList();
Set resultSet = new HashSet();
for(int i=0; i<numbers.length(); i++) {
numList.add(String.valueOf(numbers.charAt(i)));
}
//순열생성
perm(numList, resultSet, 0);
//소수 확인
Iterator itr = resultSet.iterator();
while (itr.hasNext()) {
if(isPrime(itr.next())) {
answer++;
}
}
return answer;
}
//참고 (순열 생성)
public List perm(List list, Set resultSet,int pivot) {
if (pivot == list.size()) {
//System.out.println(list);
makeResultSet(list, resultSet);
}
for (int i = pivot; i < list.size(); i++) {
swap(list, i, pivot);
perm(list, resultSet, pivot + 1);
swap(list, i, pivot);
}
return list;
}
public void swap(List list, int i, int j) {
String a = list.get(i);
String b = list.get(j);
list.set(i, b);
list.set(j, a);
}
// 순열별 경우의수
public Set makeResultSet(List numList,Set resultSet){
// prefix 를 정하고 뒤를 순서대로 붙임
// 다음 프리픽스로 사용한 인덱스를 제거하고 반복하면서 리절트셋에 에드
for(int k=0; k<numList.size() ; k++) {
int fixIdx = k;
resultSet.add(Integer.valueOf(numList.get(k)));
List tempNumList = new ArrayList();
//고정 값을 제외하 나머지 요소를 담을 리스트를 생성합니다.
for(int i=fixIdx+1; i<numList.size();i++) {
tempNumList.add(numList.get(i));
}
for(int i=0; i< tempNumList.size();i++) {
// 두번째로 배치할 인덱스 == i
// 두번째 배치할 요소를 고려해서 큐를 생성합니다.
Queue q = new LinkedList();
List tempNumList2 = new ArrayList();
String resultNum = numList.get(fixIdx);
resultNum += tempNumList.get(i);
for(int j=0; j<tempNumList.size(); j++) {
if(i != j) {
resultNum += tempNumList.get(j);
}
}
resultSet.add(Integer.valueOf(resultNum));
makeResultSet(tempNumList,resultSet);
}
}
return resultSet;
}
private boolean isPrime(int num) {
if (num < 2) return false;
if (num == 2) return true;
if (num % 2 == 0) return false;
/**
* num 이 p * q 라고 할때 한 수는 항상 sqrt(num) 이하의 값을 갖는다. (ex, num = 24, p = [1, 2, 3, 4], q = [6, 8, 12, 24])
* 따라서 num 이 sqrt(num) 이하의 값중 하나로 나눠지는지 체크한다. (ex, 24 가 4 이하의 숫자로 나눠지는지 체크,, 1,2 는 예외)
*/
// 참고
int sqrtn = (int) Math.sqrt(num);
for (int i = 3; i <= sqrtn; i += 2) {
if (num % i == 0) return false;
}
return true;
}
'알고리즘' 카테고리의 다른 글
[JAVA ]프로그래머스 - 오픈채팅방(openChatRoom) 42888 (0) | 2020.01.13 |
---|