[Day23]JAVA 프로그래머스 소수 찾기(완전탐색, 백트래킹)

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

프로그래머스

 

프로그래머스 소수 찾기 문제를 해결하기 위해서는 백트래킹 알고리즘 과 소수에 대해서 알아야한다.

 

먼저 백트래킹 과 소수에 대해서 알아보겠다. 

---

⭐백트래킹
문제를 풀 때 모든 경우의 수를 체크(완전탐색) 하면서 , 해가 아닌 케이스의 경우를 만나면 그 이전의 상태로 되돌아가서 다른 케이스를 체크하는 알고리즘 이다.

1. 깊이 우선 탐색(DFS) : DFS 와 같이 재귀적으로 깊숙하게 확장해나가면서 해를 찾는다. 하지만 DFS 와 달리 해당 경로가 틀린 해답이라는 것을 알아챈다면 바로 이전 상태로 Backtracking 한다.
2. 유망성(Promising) 판단과 가지치기 : 현재 상태가 해를 찾을 수 있는 상태(모든 경우를 다 확인한 상태)인지 판단하고, 만약 그러하지 않으면  더 이상 해당 경로를 탐색하지 않고 이전 상태로 되돌아가서 다음 경로를 탐색한다. 

즉, 조건을 걸어 해당 조건을 만족하며 다음 경로에 대하여 재귀호출을 하도록 설계된 것이다. 
완전 탐색이 필요한 경우, 순열 또한 조합과 관련된 경우, 0 또는 1로 결정되는 의사 결정의 집합을 구하는 문제 등에서 백트래킹을 사용할 수 있다. 

 

⭐소수 

소수는 1과 자기자신만을 약수로 가지는 수이다. 
소수에는 2 , 3, 5, 7 , 11.. 과 같은 수들이 있다. 
4~100 이내의 숫자들은 위의 2와 3으로 나누었을때 나머지가 있는 경우 소수 라고 계산 할 수 있다. 

하지만 그 이상의 숫자가 커지면 소수와 소수로 약수를 만드는 경우가 있다.

예를들면 143 = 13 x 11 이다 . 13도 약수 11도 약수 이므로 위의 같은 방식으로는 예외가 나와 소수를 찾기에 적합하지 못한 방식이다.

 

그럼 예외 없이 소수를 구하는 방법은? 

짝수 와 홀수 두 가지 경우를 예를 들어 보겠다. 

[24 의 약수]

1 x 24 = 24
2 x 12 = 24
3 x 8 = 24
4 x 6 = 24
6 x 4 = 24
8 x 3 = 24
12 x 2 = 24
24 x 1 = 24

 

[15의 약수]
1 x 15 = 15
3 x 5 = 15
5 x 3 = 15
15 x 1 = 15

 

짝수 , 홀수 두 경우를 비교를 해보면 각 등식이 대칭적인 형태를 보여주고 있다. 
수의 제곱근(루트) , 더 쉽게 말해 가운데 반 딱 잘라서나누어지는 값이 있는지 확인하면 된다. (정확히 제곱근은 중간이 아니다.. 뉘양스가.. 그렇다는 것) 

 

143 으로 다시 예시를 들면 143의 제곱근은 11 이다 
 2 부터 11까지 나누어 보면 
143 % 11 = 0 으로 나누어 떨이지는 것을 확인 할 수 있다. 나누어 떨어지는 143은 실수가 아니다. 

 

제곱근 구하는 공식은  Math.sqrt()

public static boolean isPrime(int n) {
        boolean result = true;
        
        // 2부터 n의 제곱근까지 나누어 떨어지는지 확인
        for (int i = 2; i <=(int) Math.sqrt(n); i++) {
            if (n % i == 0) {
                result = false; // 나누어 떨어지면 소수가 아님
                break;
            }
        }
        
        return result; // 소수 여부 반환
}

 

 

백트래킹 과 소수에 대해서 이해가 되었다면 백준의 소수 찾기 문제를 풀 수 있다!! 

---

🌘문제 이해하기 

• 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을때 , 종이 조각으로 만들 수 있는 소수가 몇개인지 return

---

🌗문제 자세히보기

 

1. 문자열을 char 형태로 조각조각 나눠서 배열에 저장해 둔다. 
2. 처음 시작 숫자를 정하고 재귀호출을 하며 그 뒤에 올 수 있는 다음 숫자를 찾는다.(방문했으면 넘어가기)
3. 백트래킹을 활용하여 더 이상 다음 숫자가 없거나 적합하지 않은 숫자 인 경우 이전 자리로 되돌아가 다른 숫자를 체크한다.(되돌아가면서 방문 취소하기) 
4. 만들 수 있는 모든 경우의 수를 구한다.(중복 없이)
5. 만든 수 중에 소수 인 것만 추린다. 
6. 추려진 소수들의 개수를 return

---

🌕 최종코드

import java.io.*;
import java.util.*;
public class Main{ 
    public static void main(String[] args) throws IOException
    {
        //소수 찾기 (완전탐색)      
        String num = "143";

        System.out.println(solution(num));
    }    
   
    public static int solution(String numbers)
    {
        int answer = 0;

        char[] numberArr = new char[numbers.length()];
        boolean [] visited = new boolean[numbers.length()];
        List<String> result = new ArrayList<>();

         //종이 조각으로 만들 수 있는 숫자들 배열에 저장
        for(int i=0;i<numbers.length();i++)
        {   
            numberArr[i] = numbers.charAt(i);
        }    

        for(int i=0;i<numberArr.length;i++)
        {
            if(numberArr[i] == '0') //0이 맨 처음에 존재 할 수 없다.
                continue; 

            //첫 숫자 결정
            makeNum(numberArr, visited, result, i, String.valueOf(numberArr[i]));
        }

        for(String s : result)
        {
            int n = Integer.parseInt(s);

            if(n > 1 && isPrime(n))
            {
                System.out.println(n);
                answer++;    
            }
        }

        return answer;
    }

    public static boolean isPrime(int n) {
        boolean result = true;
        
        // 2부터 n의 제곱근까지 나누어 떨어지는지 확인
        for (int i = 2; i <=(int) Math.sqrt(n); i++) {
            if (n % i == 0) {
                result = false; // 나누어 떨어지면 소수가 아님
                break;
            }
        }
        
        return result; // 소수 여부 반환
    }


    // List<String> result : 만들어진 모든 숫자를 담을 배열
    // startIndex : 조회할 다음 숫자 인덱스
    // current : 현재 만들어진 숫자
    public static void makeNum(char[]numberArr , boolean[] visited ,List<String> result, int startIndex , String current)
    {
        //현재 숫자 방문처리
        visited[startIndex] = true;
       
        if(!result.contains(current))
            result.add(current);

        for(int i=0;i<numberArr.length;i++)
        {
            if(!visited[i]) //사용하지 않은 숫자
            {
                makeNum(numberArr , visited,result, i,current+numberArr[i]);
            }
        }

        //백트레킹
        visited[startIndex] = false;        
    }
    
}