[ 프로그래머스] LV2 소수찾기 JAVA 풀이

 

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

프로그래머스

 

솔직히 이 코드가 최선의 코드는 아니다.

특히 pnum() 부분은 에라토스테네스의 체가 생각났지만 구현방법이 기억나지 않아 그냥 깡 구현했다.

이러면 안돼!! 인생은 복습이야!

접근법 : 

**1) 어떻게 풀 것인가?**

1. 자릿수를 하나씩 더해가며 재귀함수를 호출한다.

2. 중복으로 뽑는것은 안 되므로 check[] 를 사용하여 사용했는지 안 했는지를 체크하고, 백트래킹을 활용한다.

3. 소수 -> 2,3,5,7..... 의 조건에 맞게 코드를 작성한다.

3.1 미지수 k<2 라면 소수 아님

3.2 미지수k를 미지수n 으로 나누었을 때 나머지가 0이면 소수아님 ( n은 2이상 k 미만이다);

**2) 시간복잡도**

 

**3) 공간복잡도**

 

**4) 풀면서 놓쳤던점**

1. set 자료구조 안 쓰고 중복방지 코드 직접 구현했음. 근데 시간이 넘 걸리길래 이걸 어케 줄이지..하다가 뒤늦게 set 생각남.

2. 에라토스테네스의 체

 

**5) 이 문제를 통해 얻어갈 것**

어떻게 구현해야할지 머릿속에 있는데도 그걸 코드로 구현하려니까 너무 어려웠다. 

나는 인텔리제이 디버깅의 노예였다..... 현타가 제대로 왔지만 어쩔거야~? 자책할 시간에 공부하면 되는거야~

**

set자료구조에 대한 공부

에라토스테네스의 체 에 대한 공부

import java.util.*;

class Solution {
    
    static int answer;
    static Set<Integer> numberSet;
    
    public int solution(String numbers) {
        
        String[] list = numbers.split("");
        int[] check = new int[numbers.length()];
        numberSet= new HashSet<Integer>();
        
        permutation(list,check,"",0);
        pnum(numberSet);
        return answer;
    }
    public static void permutation(String[] list, int[] check, String s, int count){
        if(!s.isEmpty()){
            numberSet.add(Integer.parseInt(s));
        }
        if(count == list.length) return;   

        for(int j=0; j<list.length; j++){
            if(check[j] != 1){
                check[j] = 1;
                permutation(list, check,s+list[j],count+1);
                check[j] = 0;
            }
            }
    } 
    public static void pnum(Set<Integer> numberSet){
        boolean pnum = false;
        for(int c : numberSet){
            if(c ==2 || c ==3){
                pnum = true;
            }
            else{
                for(int i=2; i<c; i++){
                    if(c%i == 0){
                        pnum= false;
                        break;
                    }
                    else{
                        pnum = true;
                    }
                }  
            }
            if(pnum){
                answer++;
            }
        }
    }
    
}