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

문제 설명

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

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

 

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbersreturn

"17"	3
"011"	2

 

입출력 예 설명

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

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

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

 

 

 

문제풀이

 

 

먼저 내가 생각한 방법

1. 문자열 numbers를 잘라서 모음.

2. 1개, 2개, ...,n개의 길이가 되도록 모든 경우의 수를 통해 이어 붙인다.

3. 맨 앞자리가 0인 경우를 판별하여 제외한다.

4. 나눗셈을 통해 소수를 판별한다.

5. 이를 세서 return 한다.

 

.

.

.

 

이대로 구현하려니 복잡한 부분이 많았다. 

발상은 좋았으나 내가 쓴 과정들 뜯어보면 사실상 3번, 5번 정도는 코드 1~2줄로 끝내야 하는 부분이라 별건 아니고 (ex. if(chs[0]=='0')return;, answer++;). 추가로 Integer.parseInt( ) 메소드로 정수변환이 가능> 011 == 11 판별 

 

 

 

 

특히 자바의 기본 개념들과 재귀를 유연하게 활용해야겠다고 생각이 들었다.

또한, 2번 부분 -> 조합+재귀 개념 필요 + dfs

 

 

 

자바로 갑자기 푸려니 여러 개념들도 너무 헷갈리고 삽질을 많이해서 최대한 푼 부분만 작성하였고,  타 블로그 참고를

많이하며 공부하였다.

 

 

(처음 해보고 안돼서 두번 시도함)

 

 

import java.util.*;

class Solution{
    
    int answer;
    boolean []check = new boolean[10];
    ArrayList<Integer>arr = new ArrayList<>();
    
    
    
   public void perm(String str, String tmp, int m){
       if(tmp.length() == m){
           int num=Integer.parseInt(tmp); //문자를 숫자로 변환해줌
           if(!arr.contains(num))
               arr.add(num);
           return;
       }else{
           for(int i=0;i<str.length();i++){
               if(!check[i]){
                check[i]=true;
                tmp+=str.charAt(i);
                perm(str,tmp,m);
               check[i]=false;
               tmp=tmp.substring(0,tmp.length()-1);
               }
           }
       }
   }
    
    public void isPrime(int n){
        if(n==0||n==1)return;
        for(int i=2;i<=n;i++){
            if(n % i ==0) return;
        }
        answer++;
    }
    
    
    public int solution(String numbers){
        String tmp="";
        for(int i=0;i<numbers.length();i++){
            perm(numbers,tmp,i+1);
        }
        for(int i=0;i<arr.size();i++){
            isPrime(arr.get(i));
            
        }
        return answer;
    }
    
    
}

 

 

 

 

 

 

 

 

 

 

 

 

https://hoho325.tistory.com/201

[완전탐색, 소수, 순열] level2 프로그래머스 소수 찾기 자바 풀이

 

https://fbtmdwhd33.tistory.com/227

[프로그래머스,Level 2] 소수 찾기(JAVA 구현)