소수 찾기

Seongjin Jo·2023년 5월 13일
0

프로그래머스 LV2

목록 보기
6/28

문제

풀이

import java.util.*;

class Solution {
    static char[] crr;
    static boolean[] ch;
    static int cnt=0;
    static ArrayList<Integer> arr = new ArrayList<>();
    
    public static boolean isPrime(int sum){
        if(sum==0 || sum==1) return false;
        else{
            for(int i=2; i<sum; i++){
                if(sum%i==0) return false;
            }
        }
        return true;
    }
    
    public static void DFS(String sum,int length){    
        if(sum.length()==length){
            int num = Integer.parseInt(sum);
            if(isPrime(num)==true && !arr.contains(num)){
                arr.add(num);
            }
        }
        else{
            for(int i=0; i<crr.length; i++){
                if(!ch[i]){
                    ch[i]=true;
                    DFS(sum+=crr[i],length);
                    ch[i]=false;
                    sum = sum.substring(0,sum.length()-1); //초기화 
                }
            }
        }
    }
    
    public int solution(String numbers) {
        int answer = 0;
        //DFS돌려서 각각의 조합마다 -> isPrime()으로 소수 판별
        
        crr = numbers.toCharArray();
        ch = new boolean[crr.length];
        
        for(int i=0; i<crr.length; i++){
            DFS("",i+1);
        }
        
        return arr.size();
    }
}

DFS()의 대표적인 문제라고 할 수 있다. 이 문제를 해결하는 데 애를 먹었다.

어려움

  • 시간 초과. 모든 자리수의 소수를 DFS로 한번에 구하려고 하니까 시간초과가 발생
    해결법 : 각 자리수 별로 소수가 되는 경우를 찾음
  • DFS() 호출 후에 현재의 DFS()로 돌아왔을 때 현재의 문자가 원래 대로 돌아오지 않았다.
    이유 : DFS()를 호출할때 문자 sum 을 sum+=crr[i] 이렇게 '+'를 이용하여 붙여서 호출했는데, 다시 복귀할 때는 '-'는 안돼서 그런 것 같다. 그래서 '-'대신에 끝자리를 substring()을 이용하여 빼줬더니 되더라. 이 부분은 아직도 갸우뚱한 부분이다...

꼭 다시 봐야할 문제라고 생각한다. 아무튼 해결!

0개의 댓글