[알고리즘과 자료구조] JAVA - 완전탐색 소수 찾기

문제 설명

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


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


제한사항

numbers는 길이 1 이상 7 이하인 문자열입니다.

numbers는 0~9까지 숫자만으로 이루어져 있습니다.

"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.


입출력 예 설명

예제 #1

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


예제 #2

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

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


문제풀이

  1. import java.util.*;
  2. class Solution {
  3. public int solution(String numbers) {
  4. int answer = 0;
  5. char[] numsCArr = numbers.toCharArray();
  6. // 경우의 수를 모두 담을 ArrayList
  7. ArrayList<Integer> numsArr = new ArrayList<>();
  8. for ( int i=1; i<=numsCArr.length; i++){
  9. // 재귀함수 호출
  10. permutation(numsCArr, numsArr, 0, i);
  11. }
  12. // numsArr 리스트에 추가된 배열 값에서 소수를 찾는다.
  13. for( int i=0; i<numsArr.size(); i++ ){
  14. // 소수이면 answer++
  15. if (!decimal(numsArr.get(i))){
  16. answer++;
  17. }
  18. }
  19. return answer;
  20. }
  21. // 순열 재귀함수
  22. public void permutation(char[] numsCArr, ArrayList<Integer> numsArr, int depth, int length){
  23. // depth와 length가 같으면 list에 값을 추가.
  24. if( depth == length ){
  25. StringBuffer sb = new StringBuffer();
  26. for ( int i=0; i<length; i++){
  27. sb.append( numsCArr[i] );
  28. }
  29. if( !numsArr.contains(Integer.parseInt( sb.toString())) && Integer.parseInt( sb.toString()) > 1 ){
  30. numsArr.add( Integer.parseInt( sb.toString() ));
  31. }
  32. return;
  33. }
  34. for ( int i=depth; i<numsCArr.length; i++){
  35. // testcase "17"의 경우 0번째, 0번째를 스왑해서 17 그대로 삽입
  36. // 다음은 0, 1을 스왑 "71" 삽입
  37. swap(numsCArr, i, depth);
  38. permutation(numsCArr, numsArr, depth+1, length);
  39. // 다시 swap 해서 배열 index를 제위치로
  40. swap(numsCArr, i, depth);
  41. }
  42. }
  43. // 순열 재쉬함수에서 swap
  44. public void swap (char[] numsCArr, int i, int j){
  45. char tmp = numsCArr[i];
  46. numsCArr[i] = numsCArr[j];
  47. numsCArr[j] = tmp;
  48. }
  49. // 소수 찾기
  50. public boolean decimal(int num) {
  51. boolean decimal = false;
  52. for ( int i=2; i<num; i++ ){
  53. // i로 나눈 나머지가 0이면 소수가 아니다.
  54. if( num % i == 0 ){
  55. decimal = true;
  56. break;
  57. }
  58. }
  59. return decimal;
  60. }
  61. }



* 파트너스 활동을 통해 일정액의 수수료를 제공받을 수 있음
작성자 소개
초이 프로필
WrapUp 블로거

초이

반려견을 좋아하고, 차를 좋아하고, 여행을 좋아하고, 맛집을 찾아 즐기는 웹 개발자 입니다^^