99클럽 코테 스터디 21일차 TLI-(완전탐색)

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

🚨오늘의 학습🚨

⭐️완전탐색⭐️

모든 경우의 수를 시도하여 정답을 찾는 알고리즘이다.
Brute Force라고도 한다

🗝️ 조합 가능한 모든 경우의 수를 찾는다 ≒ 순열

• 순열 = 재귀 = DFS
• 🔅 백트랙킹(상태복원)
  • 다른 경로를 탐색 가능하도록 만듦
  • 모든 경우를 탐색하기 위해 필수적

ex)

used[i]=true;
dfs(Integer.parseInt(cardNum));
used[i]=false; // 상태 복원 = 백트랙킹

🗝️ 경우의수 중 소수를 찾는다

🔅에라토스테네스의 체

1 or 자기자신 이외의 수로 나누어진다면 소수가 아니다.

🗝️ 자료구조: Set

순서가 없고 중복을 허용하지 않는다

"01"=="1"은 같은 수 이므로 중복을 방지 ==> Set!!

import java.io.*;
import java.util.*;

public class P_Permutation {
    static int[] cards;

    static Set<Integer> nums = new HashSet();

    static int depth = 0;

    static Boolean[] used;


    // 순열
    // 카드로 만들 수 있는 모든 숫자 구하기
    public static void main(String[] args)throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 카드 개수
        int cardCnt = Integer.parseInt(st.nextToken());

        cards = new int[cardCnt];

        int answer = 0;

        for(int i=0 ;i <cardCnt; i++){
            st= new StringTokenizer(br.readLine());

            cards[i] = Integer.parseInt(st.nextToken());
        }


        for(int i=0; i< cards.length; i++){
            depth=0;
            used = new Boolean[cardCnt];
            Arrays.fill(used,false);

            nums.add(cards[i]);
            used[i]=true;
            dfs(cards[i]);

        }
        System.out.println("개수 :"+nums.size());

        for (Integer num : nums) {
            System.out.println("생성 : "+num);
        }

        for (Integer num : nums) {
            int cnt = 0;
			// 에라토스테네스의 체 
            for(int i=2; i<Math.sqrt(num); i++){
            	// 소수판별
                if(num%i==0){
                    cnt++;
                }
            }

            if(cnt==0 && num!=0 && num !=1){
                System.out.println(num);
                answer++;
            }
        }

    }

	// 순열 재귀함수
    public static void dfs(int num){
        if(depth==nums.size()){
            return;
        }

        depth++;

        for(int i=0; i<cards.length; i++){
            if(!used[i]){
                used[i]=true;
                String cardNum = new StringBuilder().append(num).append(cards[i]).toString();
                nums.add(Integer.parseInt(cardNum));
                dfs(Integer.parseInt(cardNum));
                used[i]=false;

            }

        }


    }


}