[Programmers] 소수 찾기 - Java

[Programmers] 소수 찾기 - Java

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

문제

문제 설명

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

풀이

풀이 과정

완전 탐색을 위해 순열 알고리즘을 이용하고 소수를 판단하기 위해 에라토스테네스의 체 알고리즘을 이용

먼저 에라토스테네스의 체로 소수를 판별할 배열을 세팅한다

public int solution(String numbers) { int answer = 0; prime = new boolean[10000001]; //소수 판별 알고리즘 isPrime(); } //소수 판별 알고리즘 private static void isPrime() { prime[0] = prime[1] = true; for(int i = 2; i < Math.sqrt(prime.length); i++) { if(prime[i]) { continue; } for(int j = i + i; j < prime.length; j += i) { prime[j] = true; } } }

마지막 깊이 까지 탐색을 완료 하였을 때 조합된 문자열을 정수형으로 변환 후 소수 여부를 판단한 다음 set에 담아 중복을 제거하도록 순열 알고리즘 구현

//순열 알고리즘 private static void perm(String[] s, int depth, int k, Set set) { /* * s = 숫자를 뽑아올 배열 * depth = 탐색 깊이 * k = 뽑아올 숫자의 갯수 * set = 생성된 순열 데이터 */ if(depth == k) { //원하는 개수의 숫자까지 탐색하면 종료 StringBuilder sb = new StringBuilder(); for(int i = 0; i < k; i++) { sb.append(s[i]); } int num = Integer.parseInt(sb.toString()); //소수 판단 if(!prime[num]) { set.add(num); return; } } else { for(int i = depth; i < s.length; i++) { swap(s, i, depth); // 자리를 바꾼 후 perm(s, depth + 1, k, set); // 다음 깊이 순열 탐색 swap(s, i, depth); // 원래대로 복구 } } } //스왑 알고리즘 private static void swap(String[] s, int i, int depth) { String temp = s[i]; s[i] = s[depth]; s[depth] = temp; }

종이 조각을 하나부터 종이 조각 최대 개수만큼 뽑아 탐색할 수 있도록 반복하며 순열 알고리즘을 실행

public int solution(String numbers) { int answer = 0; prime = new boolean[10000001]; //소수 판별 알고리즘 isPrime(); String[] s = numbers.split(""); Set set = new HashSet<>(); //순열 알고리즘 (1자리 수부터 최대길이 만큼) for(int i = 1; i <= s.length; i++) { perm(s, 0, i, set); } }

최종적으로 만들어진 set의 size를 return

answer = set.size(); return answer;

최종 코드

import java.util.*; class Solution { static boolean[] prime; public int solution(String numbers) { int answer = 0; prime = new boolean[10000001]; //소수 판별 알고리즘 isPrime(); String[] s = numbers.split(""); Set set = new HashSet<>(); //순열 알고리즘 (1자리 수부터 최대길이 만큼) for(int i = 1; i <= s.length; i++) { perm(s, 0, i, set); } answer = set.size(); return answer; } //순열 알고리즘 private static void perm(String[] s, int depth, int k, Set set) { /* * s = 숫자를 뽑아올 배열 * depth = 탐색 깊이 * k = 뽑아올 숫자의 갯수 * set = 생성된 순열 데이터 */ if(depth == k) { //원하는 개수의 숫자까지 탐색하면 종료 StringBuilder sb = new StringBuilder(); for(int i = 0; i < k; i++) { sb.append(s[i]); } int num = Integer.parseInt(sb.toString()); //소수 판단 if(!prime[num]) { set.add(num); return; } } else { for(int i = depth; i < s.length; i++) { swap(s, i, depth); // 자리를 바꾼 후 perm(s, depth + 1, k, set); // 다음 깊이 순열 탐색 swap(s, i, depth); // 원래대로 복구 } } } //스왑 알고리즘 private static void swap(String[] s, int i, int depth) { String temp = s[i]; s[i] = s[depth]; s[depth] = temp; } //소수 판별 알고리즘 private static void isPrime() { prime[0] = prime[1] = true; for(int i = 2; i < Math.sqrt(prime.length); i++) { if(prime[i]) { continue; } for(int j = i + i; j < prime.length; j += i) { prime[j] = true; } } } }

from http://hyojun.tistory.com/24 by ccl(A) rewrite - 2021-11-30 14:27:52