[프로그래머스/Lv. 2] 소수 찾기 (JAVA)

🔺 문제

프로그래머스

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
class Solution {
    static ArrayList<Integer> arr = new ArrayList<>();
    static boolean[] visited = new boolean[7];
 
    public int solution(String numbers) {
        int answer = 0;
        
        // 📍 몇 자리 수를 만들건지에 대한 반복 (예 : 011의 경우: 1~3자리)
        for(int i = 0 ; i < numbers.length() ; i++) {
            back(numbers, "", i + 1);
        }
        
        for(int i = 0 ; i < arr.size() ; i++) {
            if(isPrime(arr.get(i))) answer++;
        }       
        
        return answer;
    }
    
    // 백트래킹 메소드
    private static void back(String str, String tmp, int depth) {       
        if(depth == tmp.length()) {
            int num = Integer.parseInt(tmp);
            if(!arr.contains(num))  arr.add(num);                
        }
        
        for(int i = 0 ; i < str.length() ; i++) {
            if(!visited[i]) {
                tmp += str.charAt(i); // 임시 변수에 tmp 붙이며 숫자 조합
                
                visited[i] = true;
                back(str, tmp, depth);
                visited[i] = false;
                
                tmp = tmp.substring(0, tmp.length() - 1); // 🔔 이전 상태로 돌아가기 위해 tmp 변수에서 마지막 자리 숫자 제외하고 갱신
            }
        }
    }
    
    // 소수 판단 메소드 (에라토스테네스의 체 활용)
    private static boolean isPrime(int n) {
        if(n < 2) return false;
        
        for(int i = 2 ; i <= (int)Math.sqrt(n) ; i++) {
            if(n % i == 0) return false;
        }
        
        return true;
    }
}

✅ 해결 아이디어
✔ 백트래킹 + 브루트포스
1) 백트래킹 함수 구현 시, String 값을 Integer 값으로 변경해 찾을 수 있는 값 전부를 중복 없이 리스트에 담는다.
2) 리스트에 담긴 값들을 소수 판단하여 센다. 

 

- Line 38 | tmp.length() - 1하는 이유 : tmp 문자열의 마지막 문자를 제거해 이전 상태로 돌아가기 위함

 

---

🔺 다른 풀이들

- 자세한 설명 굿..

import java.util.ArrayList;

class Solution {

    public static String[] arr;
    public static int count = 0;
    static boolean[] check = new boolean[7];
    static ArrayList<Integer> arr2 = new ArrayList<>();

   public static boolean isPrime(int num) {
        if (num == 0) return false;
        if (num == 1) return false;
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) return false;
        }
        return true;
    }

    public static int solution(String numbers) {

        String temp = "";
        // 2. 몇 자리의 수를 만들 지에 대한 반복, 011의 경우 1~3자리의 다양한 숫자 조합이 가능.
        for (int i = 1; i <= numbers.length(); i++) {
            rec(numbers, temp, i);
        }

        return count;
    }

    public static void rec(String n, String temp, int len) {


        if (temp.length() == len) {
            // 12. ArrayList에 이미 존재하는 값인지를 확인해 중복값 삽입을 방지.
            if (!arr2.contains(Integer.parseInt(temp))) {
                arr2.add(Integer.parseInt(temp));
                if (isPrime(Integer.parseInt(temp)))
                    count++;
            }
            return;
        }
        // 4. n으로 전달 된 numbers를 탐색.
        for (int j = 0; j < n.length(); j++) {
            // 5. 이미 방문한 인덱스면 패스.
            if (check[j]) continue;
            // 6. 임시 변수 temp에 붙여나가며 숫자를 조합.
            temp += n.charAt(j);
            // 7. temp에 붙였기 때문에 방문처리.
            check[j] = true;
            // 8. 재귀, 앞서 붙인 temp변수와 현재 몇 자리의 수를 만드는지에 대한 정보인 len 변수를 전달.
            rec(n, temp, len);
            // 9. 조합이 완료되면 직전의 방문처리한 인덱스를 false로 변경.
            check[j] = false;
            // 10. temp 변수에서 마지막 자리의 숫자를 제외하고 갱신.
            temp = temp.substring(0, temp.length() - 1);

        }
    }
}

 

 

- HashSet 이나 TreeSet을 사용하신 경우들도 있당

[프로그래머스] 소수 찾기 (완전탐색 Lv. 2) - 자바 Java

(Java) 프로그래머스 소수찾기_L2

---

💬 느낀 점

훔 백트래킹 문제인 건 파악했는데 이걸 문자열 길이가 다를 때마다 어떻게 수행해야 할까,,, 했더니

아래처럼 작성해주면 되는 것이었다...

for(int i = 0 ; i < numbers.length() ; i++) {
    back(numbers, "", i + 1);
}

 

tmp 문자열 갱신하는 과정도 필요했고...

복습하기 좋은 문제 같다!

 

1회독	2회독	3회독	4회독	5회독
V	10.16

 

 

(+ 10.16 2회독)

import java.util.*;
 
class Solution {
    static String numbers;
 
    static Set<Integer> answer = new HashSet<>();  // 소수 집합 (중복 제거)
    static boolean[] visited = new boolean[7];
    
    public int solution(String numbers) {
        this.numbers = numbers;
        
        // 몇 자리 수 만들건지
        for(int i = 0 ; i < numbers.length() ; i++) {
            back("", 0, i + 1);
        }
 
        return answer.size();
    }
    
    // 숫자 조합 만들 백트래킹 메소드
    private static void back(String str, int depth, int goal) { // depth : 고른 갯수, goal : 목표 자릿수
        if(depth == goal) {
            int tmp = Integer.parseInt(str);
            
            if(!answer.contains(tmp) && isPrime(tmp)) {
                answer.add(tmp);
            }
            return;
        }
        
        // numbers의 한 글자씩 브루트포스
        for(int i = 0 ; i < numbers.length() ; i++) {
            if(!visited[i]) {
                str += numbers.charAt(i);   // 임시 변수에 붙이며 숫자 조합 생성
                
                visited[i] = true;
                back(str, depth + 1, goal);
                visited[i] = false;
                
                str = str.substring(0, str.length() - 1);   // 🔔 이전 상태로 돌아가고자 마지막 자리 숫자 제외하고 갱신
            }                
        }
    }
    
    // 소수 판별 메소드
    private static boolean isPrime(int num) {
        if(num <= 1) return false;
        
        for(int i = 2 ; i * i <= num ; i++) {
            if(num % i == 0)    return false;
        }
        return true;
    }
}

 

---

(참고)

[프로그래머스 Level2] 소수 찾기 (JAVA)