알고리즘/프로그래머스

[프로그래머스] 소수 찾기

쿠큭다스 2022. 1. 6. 14:23
728x90

 

문제 설명

 

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

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

풀이 방법

 

종이 조각으로 만들 수 있는 모든 수를 조사해야 하므로 순열을 이용하였다.

또한, 처음에 주어지는 값을 문자열이고 소수를 판별해야 할때에는 정수형으로 변환해야 하는 과정이 필요하다.

 

변환되는 값이 소수인지 판별할 때는 중복되는 값은 포함시키면 안되기 때문에 이를 ArrayList를 두 번 사용하여

중복되는 값을 없애주는 과정을 하였고, 마지막에는 ArrayList에서 소수인 경우 answer를 증가시켜 주었다.

 

작성 코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import java.util.*;
 
     class Solution {
 
        static ArrayList<Integer> list=new ArrayList<>();
 
        public int solution(String numbers) {
            int answer = 0;
            ArrayList<Integer> result=new ArrayList<>();
            char[] ch=new char[numbers.length()];
 
            for (int i=0;i<numbers.length();i++){
                ch[i]=numbers.charAt(i);
            }
 
            for(int i=0;i<numbers.length();i++){
                permutation(ch,0,i+1,numbers.length());
            }
 
            for(int i=0;i<list.size();i++){
                if(!result.contains(list.get(i))){
                    result.add(list.get(i));
                }
            }
 
            for(int i=0;i<result.size();i++){
                boolean isPrime=false;
                int num=result.get(i);
                for(int j=2;j<num;j++){
                    if(num%j==0){
                        isPrime=true;
                        break;
                    }
                }
                if(!isPrime){ // 소수인 경우
                    answer++;
                }
            }
 
            return answer;
        }
 
        // depth : 현재 탐색하는 인덱스, r : 뽑는 개수
        static void permutation(char[] ch, int depth, int r, int length){
            if(depth==r){
                check(ch,r);
                return;
            }
            for(int i=depth;i<length;i++){
                swap(ch,depth,i);
                permutation(ch,depth+1,r,length);
                swap(ch,depth,i);
            }
        }
 
        static void swap(char[] ch, int depth, int i){
            char temp=ch[depth];
            ch[depth]=ch[i];
            ch[i]=temp;
        }
 
        static void check(char[] ch, int r){
            String number="";
 
            for(int i=0;i<r;i++){
                number+=ch[i];
            }
 
            int value=Integer.parseInt(number);
 
            if(value>1){
                list.add(value);
            }
        }
    }
 
  

 

 

728x90