소수 찾기 / 프로그래머스 코딩테스트 / programmers / level2 / 완전탐색 / Java

programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기

이번 문제는 약간은...노가다?? 로 푼 문제라고 할수도 있겠다.

 

문자열을 매개변수로 받았을때 해당 문자열은 7자리의 숫자로 이루어지고 해당 숫자들의 조합의 모든 경우의 수를 찾아서 그 숫자들 중에 소수가 몇 개인지를 찾아 리턴하는 문제다.

 

[알고리즘 Flow]

1. 1 ~ 7 자리씩 조합하는 경우의 수들을 구하는 메소드를 각각 만든다.

2. 문자열의 길이만큼 해당 메소드들을 실행시켜줄거다. (예를 들어 문자열 길이가 3이면 3자리씩 조합하는 경우의 수를 구하는 메소드까지만 실행된다.)

3. 메소드의 리턴값은 Set이고 경우의 수 만큼 반복되는 동안 모두 Set안에 넣어준다. (011, 11 같은 중복을 알아서 제거)

4. 그 다음 이터레이터로 Set의 값을 가져다 주고 반복하여 이터레이터의 모든 숫자들을 소수판별한다.

5. 소수의 총 합의 리턴한다.

 

여기서 처음에는 Set을 쓰지 않고 구현을 하려고 했었다...

그러다보니 i == j || j == k .... 이런식으로 if 조건을 걸어서 같으면 continue를 해주면서 더해주었는데,

하다보니 너무 길어지고...힘들고, 그리고 막상 디버깅해보니 번지수가 같은 경우만 넘어가니...011, 11 같은 중복이 제거될리 만무 했다.

 

하여 Set을 이용하게 된 것이다.

 

평균 처리속도는 빠르지 않았다.

그래도 이번에는 최대한 모듈화 해보려고 노력했다. (각각의 경우의 수를 구현하는 것과 소수를 체크하는 기능을 분리)

처리속도를 빠르게 하기 위해서는 

 

짝수를 모두 건너뛰고 소수체크를 하는 함수를 사용하면 될 것같은데, 아직까지는 감이 안온다.

int i = 3; i < n; i += 2 ??

하면 될 것 같은데...n이 신경쓰이네... 조금 더 연구해보자. 일단 구현성공!!!

 

[나의 코드]

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class findPrimeNum {

	public static void main(String[] args) {
		
		String numbers = "123";
		
		solution(numbers);
		
	}
	
	public static int solution(String numbers) {
        int answer = 0;
        
        Set<Integer> set = new HashSet<Integer>();
        
        char arr [] = new char [numbers.length()];
        
        for (int i = 0; i < arr.length; i++) {
			arr[i] = numbers.charAt(i);
		}
        // char 배열을 만들어서 길이만큼 담아준다.
        
        for (int i = 0; i < arr.length; i++) {
        	if (i == 0) {
        		set.addAll(count1(arr));
        	} else if (i == 1) {
        		set.addAll(count2(arr));
        	} else if (i == 2) {
        		set.addAll(count3(arr));
        	} else if (i == 3) {
        		set.addAll(count4(arr));
        	} else if (i == 4) {
        		set.addAll(count5(arr));
        	} else if (i == 5) {
        		set.addAll(count6(arr));
        	} else if (i == 6) {
        		set.addAll(count7(arr));
        	}	
		}   
        
        Iterator<Integer> itr = set.iterator();
        
        while (itr.hasNext()) {
        	if(primeCheck(itr.next())) {
        		answer++;
        	}
        }
        
        System.out.println(set);
        System.out.println(answer);
        return answer;
    }
	
	public static boolean primeCheck(int n) {
		// 소수 판별
		boolean prime = true;
		
		if (n <= 1) {
			prime = false;
		} else {
			for (int i = 3; i < n; i+=2) {
				if (n % i == 0) {
					prime = false;
					break;
				}
			}
		}			
		return prime;
	}
	
	public static Set<Integer> count1(char [] arr) {	
        // 1개씩 비교한 경우의 수
		Set<Integer> countSet = new HashSet<Integer>();
        for (int i = 0; i < arr.length; i++) {
        	
        	int chkNum = Character.getNumericValue(arr[i]);
        	countSet.add(chkNum);
		}
		return countSet;
	}
	
	public static Set<Integer> count2(char [] arr) {
		// 2개씩 묶은 경우의 수
		Set<Integer> countSet = new HashSet<Integer>();
        for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr.length; j++) {
				if (i == j || arr[i] == '0') {
					continue;
				} else {
					String temp = arr[i] + "" + arr[j];
					int chkNum = Integer.parseInt(temp);
					countSet.add(chkNum);
				}	
			}
		}
		return countSet;
	}
	
	public static Set<Integer> count3(char [] arr) {
        // 3개씩 묶은 경우의 수
		Set<Integer> countSet = new HashSet<Integer>();
        for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr.length; j++) {
				for (int k = 0; k < arr.length; k++) {
					if (i == j || j == k || i == k || arr[i] == '0') {
						continue;
					} else {
						String temp = arr[i] + "" + arr[j] + "" + arr[k];
						int chkNum = Integer.parseInt(temp);
						countSet.add(chkNum);
					}	
				}			
			}
		}
		return countSet;
	}
	
	public static Set<Integer> count4(char [] arr) {
        // 4개씩 묶은 경우의 수
		Set<Integer> countSet = new HashSet<Integer>();
        for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr.length; j++) {
				for (int k = 0; k < arr.length; k++) {
					for (int k2 = 0; k2 < arr.length; k2++) {
						if (i == j || j == k || i == k || k == k2 || k2 == j || k2 == i) {
							continue;
						} else {
							String temp = arr[i] + "" + arr[j] + "" + arr[k] + "" + arr[k2];
							int chkNum = Integer.parseInt(temp);
							countSet.add(chkNum);
						}
					}	
				}
			}
		}
		return countSet;
	}
	
	public static Set<Integer> count5(char [] arr) {
        // 5개씩 묶은 경우의 수
		Set<Integer> countSet = new HashSet<Integer>();
        for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr.length; j++) {
				for (int k = 0; k < arr.length; k++) {
					for (int k2 = 0; k2 < arr.length; k2++) {
						for (int l = 0; l < arr.length; l++) {
							if (i == j || i == k || i == k2 || i == l || j == k || j == k2 || j == l || 
								k == k2 || k == l || k2 == l) {
								continue;
							} else {
								String temp = arr[i] + "" + arr[j] + "" + arr[k] + "" + arr[k2] + "" + arr[l];
								int chkNum = Integer.parseInt(temp);
								countSet.add(chkNum);
							}
						}
					}	
				}
			}
		}
		return countSet;
	}
	
	public static Set<Integer> count6(char [] arr) {
        // 6개씩 묶은 경우의 수
		Set<Integer> countSet = new HashSet<Integer>();
        for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr.length; j++) {
				for (int k = 0; k < arr.length; k++) {
					for (int k2 = 0; k2 < arr.length; k2++) {
						for (int l = 0; l < arr.length; l++) {
							for (int l2 = 0; l2 < arr.length; l2++) {
								if (i == j || i == k || i == k2 || i == l || i == l2 ||
										j == k || j == k2 || j == l || j == l2 ||
										k == k2 || k == l || k == l2 ||
										k2 == l || k2 == l2 ||
										l == l2) {
										continue;
									} else {
										String temp = arr[i] + "" + arr[j] + "" + arr[k] + "" + arr[k2] + "" + arr[l] + "" + arr[l2];
										int chkNum = Integer.parseInt(temp);
										countSet.add(chkNum);
									}
							}		
						}				
					}	
				}
			}
		}
		return countSet;
	}
	
	public static Set<Integer> count7(char [] arr) {
        // 7개씩 묶은 경우의 수
		Set<Integer> countSet = new HashSet<Integer>();
        for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr.length; j++) {
				for (int k = 0; k < arr.length; k++) {
					for (int k2 = 0; k2 < arr.length; k2++) {
						for (int l = 0; l < arr.length; l++) {
							for (int l2 = 0; l2 < arr.length; l2++) {
								for (int m = 0; m < arr.length; m++) {
									if (i == j || i == k || i == k2 || i == l || i == l2 || i == m ||
											j == k || j == k2 || j == l || j == l2 || j == m ||
											k == k2 || k == l || k == l2 || k == m ||
											k2 == l || k2 == l2 || k2 == m ||
											l == l2 || l == m ||
											l2 == m) {
											continue;
										} else {
											String temp = arr[i] + "" + arr[j] + "" + arr[k] + "" + arr[k2] + "" + arr[l] + "" + arr[l2] + "" + arr[m];
											int chkNum = Integer.parseInt(temp);
											countSet.add(chkNum);
										}
								}
							}		
						}				
					}	
				}
			}
		}
		return countSet;
	}

}

 

---

 

[깃허브]

https://github.com/RUCKUSJERRY/practiceOfJava/blob/main/Prs_Pratice/src/com/level02/findPrimeNum.java

RUCKUSJERRY/practiceOfJava