99클럽 코테 스터디 10일차 TIL + 완전탐색/DFS/프로그래머스 [소수 찾기] JAVA풀이

 

 

 

 

 

 

1. 오늘의 학습 키워드

---

 

완전탐색

DFS

 

 

2. 오늘의 학습 문제 

---

문제

---

 

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

프로그래머스

 

 

코드

---

import java.util.*;

class Solution {
    static ArrayList<Integer> arr = new ArrayList<>();
    static boolean[] check = new boolean[7];
        
    public int solution(String numbers) {
        int answer = 0;
         for(int i=0; i<numbers.length(); i++){
            dfs(numbers,"",i+1);
        }
        
        for(int i=0; i<arr.size(); i++){
            if(prime(arr.get(i))) answer++;              
        }
        
        return answer;
    }
    	//백트래킹
	static void dfs(String str, String temp, int m) {
            if(temp.length() == m){
                int num = Integer.parseInt(temp);
                if(!arr.contains(num)){
                    arr.add(num);
                }
            }
        
            for(int i=0; i<str.length(); i++){
                if(!check[i]){
                    check[i] = true;
                    temp += str.charAt(i);
                    dfs(str, temp, m);
                    check[i] = false;
                    temp = temp.substring(0, temp.length()-1);
                }
            }
		
	}
    
    static boolean prime(int n){
        if(n<2) return false;
        
        for(int i=2;i<= Math.sqrt(n) ; i++){
            if(n %i ==0)
                return false;
        }
        return true;
    }
    
    
}

 

(1) numbers에서 만들 수 있는 모든 조합을 찾기

(2) 소수인지 판단하기

 

이 두가지로 나누어 코드를 작성하려했다. 단계별로 나눈 것은 좋았지만, (1) 부분에서 막혀서 풀이를 보게 되었다. 

백트래킹은 "DFS+특정조건에 해당하면 돌아가기"인 것으로, 완전 탐색을 하는 DFS보다 속도가 빠르다. 

DFS는 재귀적으로 구현할 수 있다. 

visit여부를 설정해야한다. 이 경우 visit배열에 number의 크기만큼 설정해서 해당 문자를 쓰고 있는지를 판단해서 숫자를 조합했다. 

 

 

3. 오늘의 회고

---

• DFS공부를 내일 오전에 해야겠다.
• 재귀함수가 나오면 막막한 기분이드는데, 좀 더 친해져야겠다. 
• 다시 풀어볼것!