[프로그래머스] 소수찾기 (level.2) / JAVA/ 완전탐색

 

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

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

 

완전탐색 문제.

( + 백트래킹 같기도 하고!? ) 

 

1. 배열의 값을 조합하여 모든 경우의 수를 따져야한다.  -> 완전탐색으로 함수 구현 solve 

2. 최종 String 값을 int로 변환해서. 그 int가 소수인지 확인 -> 소수판단 함수 구현 isPrime

3. 소수의 수 만큼 반환 -> 반환을 어디서 할 것인지 고민! List형을 두어 최종 반환시 List에 값 저장 

---

나의 풀이법

 

1. 1부터 numbers의 길이만큼의 모든 숫자의 조합을 만들어내야 한다. 

ex) 1,2,3 

• 만들어져야 하는 모든 경우의 수 :  1, 2, 3, 12,13, 23, 123 
• 길이가 1인 경우 (1,2,3) / 길이가 2인 경우 (12, 13, 23) / 길이가 3인 경우 (1,2,3) 로 나눠서 계산해야 한다.
• 완전 탐색 함수 매개변수에 원하는 길이 모두를 넘겨줘야한다.
  • -> solve(String numbers, String tmp, int dpth, boolean[] check)
• 나는 아래처럼 이중 for문으로, 이중 for문 안에서 처음 보내줄 String도 정하고, check[j]= true로 설정하였지만, 한개의 for 문으로 사용하는 것이 더 편리할 것 같다. ( 이건 다시 복습하면서 풀어보기 ) 

 for(int i=1;i<=numbers.length();i++){
           for(int j=0;j<numbers.length();j++){
               boolean[] check= new boolean[numbers.length()]; 
               String tmp="";
               tmp+=numbers.charAt(j); 
               //System.out.println(tmp); 
               check[j]=true;
               solve(numbers,tmp,i, check);

           }
        }

 

 

 for문 하나로 굳이 변수들을 설정안하고, 함수 내에서 처음부터 차근차근 해도된다.  

// 이렇게 수정하면 좋을 것 같은 코드 - 이중 for문을 쓸 필요가 없다.
boolean[] check= new boolean[numbers.length()]; 
        for(int i=1;i<=numbers.length();i++){
           // for(int j=0;j<numbers.length();j++){
        
            String tmp="";
            //tmp+=numbers.charAt(j); 
            //System.out.println(tmp); 
            //check[j]=true;
            solve(numbers,tmp,i, check);
 
            //}
         }

 

 

 

 

 

 

 

** 아래는 내가 잘못 적어서 한참을 디버깅 했던 부분! 

check[] 도 다시 되돌려줬으니, tmp도 다시 돌려주던지 or 아예 임시 String을 넘겨주던지!!! 

 

for(int i=0;i<numbers.length();i++){
            if(check[i]==false){
                check[i]=true;
                /* 
                ✅✅ 틀린 이유. tmp에 값이 더해진 채로 계속 계산이 되었따.
                임시로 넘겨줄 String을 만들어 넘겨줘야한다.  */
                //solve(numbers,tmp+numbers.charAt(i), dpth, i, check);  
                String tmp2= tmp+numbers.charAt(i);
                solve(numbers,tmp2, dpth, check); 
                check[i]=false;
            }
        }

 

 

아래는 소수의 여부를 판단하는 함수.

굳이 num까지 확인할 필요없이, num의 제곱근까지만 확인해보면 된다!

ex. 36 -> 2~ 6 까지만 확인해보면 알 수 있다