[프로그래머스] (Java) 소수찾기 (완전탐색)

 

📑 1. 문제설명

 
입출력 예 설명
 
예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.
11과 011은 같은 숫자로 취급합니다.

---

💡 2. 접근방식

(1) 소수 판별하는 메서드 isPrime 만들기

public static boolean isPrime(int num) {
        if (num < 2) return false; // 2 미만은 소수가 아님
        for (int i = 2; i <= Math.sqrt(num); i++) { // 2부터 √num까지 확인
            if (num % i == 0) return false; // 나눠 떨어지면 소수가 아님
        }
        return true; // 나눠 떨어지지 않으면 소수
    }

 

 
Math.sqrt()
주어진 함수로 제곱근 만드는 메서드 
Square root를 줄여서 sqrt
소수인지 판별하는 방식 : 에라토스테네스의 체
 

(2) 순열 생성하는 메서드 generatePeremutations 만들기

// 순열을 생성하는 재귀 메서드
public void generatePermutations(String prefix, String str) {
    if (!prefix.isEmpty()) {
        numSet.add(Integer.parseInt(prefix)); // 현재 값을 숫자로 변환하여 Set에 추가
    }
    for (int i = 0; i < str.length(); i++) { // 
        generatePermutations(prefix + str.charAt(i), 
                             str.substring(0, i) + str.substring(i + 1));
    }
}

 
순열이니까 Permutations라고 했다. 조합(Combinatoin)은 순서가 중요하지 않을 때 쓰는 것이고 여기서는 주어진 숫자들을 모든 가능한 순서로 재배열 해서 모든 숫자들의 조합을 고려해야 하기 때문에 순열로 해 주는 것이다. 예를 들어서, "17"이 주어진 숫자라면 17과 71이 모두 고려되어야 하므로, 순열을 사용하여 가능한 모든 순서를 만들고, 그 중에서 소수인 숫자만 찾아 줄 것이다.
 
이 때 중복된 조합이 발생되는데 numSet은 중복된 값을 자동으로 제거해 주기 때문에, 동일한 순열이 여러 번 생성되더라도 Set에 한 번만 저장된다.
 
이 코드 StringBuilder 쓰면?
 
(3) 소수인 숫자의 개수를 반환할 solution 메서드 만들기

public int solution(String numbers) {
    numSet.clear(); // numSet 초기화
    
    // generatePermutations 메서드를 호출하여 숫자들의 모든 순열을 생성
    // 처음에는 빈 문자열을 prefix로 사용하고, numbers는 입력된 숫자 문자열
    generatePermutations("", numbers);

    // 소수의 개수를 셀 변수 count를 0으로 초기화
    int count = 0;
    // numSet에 저장된 숫자등 중 소수인 숫자의 개수를 세기 위해 Iterator를 사용하여 순회
    Iterator<Integer> it = numSet.iterator();
    while (it.hasNext()) {
        // numSet에 있는 각 숫자에 대해 소수 판별을 하고, 소수라면 count를 증가
        int number = it.next(); // numSet에서 다음 숫자를 가져오자
        if (isPrime(number)) count++; // 소수면 count 1증가
    }
    return count;
}

 
위에서 만들어준 generatePermutations 를 호출해서 매개변수로 받은 String을 가지고 만들 수 있는 가능한 모든 숫자 조합을 만든다. 그리고 소수의 개수를 세어 줄 변수 count에 isPrime() 값이 true면 +1씩 해 주면 된다.
 
왜 numSet을 초기화 해 주는가?
solution 메서드가 실행될 때마다 numSet을 비워주는 코드, 이 코드가 없으면 이전 실행에서 저장된 값들이 남아 있어서, 새로운 numbers 입력에 대해 정확한 계산이 불가능하기 때문이다.
 

---

⭐ 3. 정답코드(내코드)

import java.util.HashSet;
import java.util.Iterator;

class Solution {
    private HashSet<Integer> numSet = new HashSet<>();

    // 소수 판별 메서드
    public static boolean isPrime(int num) {
        if (num < 2) return false; // 2 미만은 소수가 아님
        for (int i = 2; i <= Math.sqrt(num); i++) { // 2부터 √num까지 확인
            if (num % i == 0) return false; // 나눠 떨어지면 소수가 아님
        }
        return true; // 나눠 떨어지지 않으면 소수
    }

    // 순열을 생성하는 재귀 메서드
    public void generatePermutations(String prefix, String str) {
        if (!prefix.isEmpty()) {
            numSet.add(Integer.parseInt(prefix)); // 숫자로 변환하여 Set에 추가
        }
        for (int i = 0; i < str.length(); i++) {
            generatePermutations(prefix + str.charAt(i), 
                                 str.substring(0, i) + str.substring(i + 1));
        }
    }

    // 소수의 개수 세는 solution 메서드
    public int solution(String numbers) {
        numSet.clear(); // numSet 초기화
        generatePermutations("", numbers);

        int count = 0;
        Iterator<Integer> it = numSet.iterator();
        while (it.hasNext()) {
            int number = it.next();
            if (isPrime(number)) count++;
        }
        return count;
    }

    // main 메서드 (테스트용)
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.solution("17"));  // 출력: 3 (소수: 7, 17, 71)
        System.out.println(sol.solution("011")); // 출력: 2 (소수: 11, 101)
    }
}

 

👏🏻 StringBuilder

import java.util.HashSet;
import java.util.Iterator;

class Solution {
    private HashSet<Integer> numSet = new HashSet<>();  // 숫자 순열을 저장할 Set

    // 소수 판별 메서드
    public static boolean isPrime(int num) {
        if (num < 2) return false; // 2 미만은 소수가 아님
        for (int i = 2; i <= Math.sqrt(num); i++) { // 2부터 √num까지 확인
            if (num % i == 0) return false; // 나누어떨어지면 소수가 아님
        }
        return true; // 나누어떨어지지 않으면 소수
    }

    // 순열을 생성하는 재귀 메서드
    public void generatePermutations(StringBuilder prefix, StringBuilder str) {
        // prefix가 비어있지 않으면 numSet에 숫자로 변환하여 추가
        if (prefix.length() > 0) {
            numSet.add(Integer.parseInt(prefix.toString()));
        }

        // str에 남아 있는 문자를 하나씩 선택하여 순열을 생성
        for (int i = 0; i < str.length(); i++) {
            // 현재 문자를 prefix에 추가하고 str에서 제거
            char removed = str.charAt(i);
            prefix.append(removed);
            str.deleteCharAt(i);

            // 재귀 호출로 나머지 문자들로 순열을 생성
            generatePermutations(prefix, str);

            // 백트래킹: 선택한 문자를 다시 원래 상태로 복구
            prefix.deleteCharAt(prefix.length() - 1);
            str.insert(i, removed);
        }
    }

    // solution 메서드
    public int solution(String numbers) {
        numSet.clear(); // numSet 초기화 (이전에 저장된 값 삭제)
        generatePermutations(new StringBuilder(), new StringBuilder(numbers)); // 순열 생성

        int count = 0;
        // numSet에 저장된 숫자들을 순회하면서 소수인 숫자만 카운트
        Iterator<Integer> it = numSet.iterator();
        while (it.hasNext()) {
            int number = it.next();
            if (isPrime(number)) count++; // 소수이면 count 증가
        }
        return count;  // 소수의 개수를 반환
    }
}

 

generatePermutations만 부연 설명

public void generatePermutations(StringBuilder prefix, StringBuilder str) {
    // prefix가 비어있지 않으면 numSet에 숫자로 변환하여 추가
    if (prefix.length() > 0) {
        numSet.add(Integer.parseInt(prefix.toString())); // 현재까지 만들어진 순열을 숫자로 변환하여 Set에 추가
    }

    // str에 남아 있는 문자를 하나씩 선택하여 순열을 생성
    for (int i = 0; i < str.length(); i++) {
        // 현재 문자를 prefix에 추가하고 str에서 제거
        char removed = str.charAt(i);  // str에서 i번째 문자를 선택
        prefix.append(removed);  // 선택된 문자를 prefix에 추가
        str.deleteCharAt(i);  // str에서 해당 문자를 제거

        // 재귀 호출로 나머지 문자들로 순열을 생성
        generatePermutations(prefix, str);  // 남은 문자들로 순열을 만들기 위해 재귀 호출

        // 백트래킹: 선택한 문자를 다시 원래 상태로 복구
        prefix.deleteCharAt(prefix.length() - 1);  // 마지막으로 추가한 문자를 prefix에서 제거
        str.insert(i, removed);  // 삭제된 문자를 다시 str에 삽입하여 원래 상태로 복구
    }
}

 

👏🏻 좋아요 제일 많이 받은 코드

import java.util.HashSet;
class Solution {
    public int solution(String numbers) {
        HashSet<Integer> set = new HashSet<>();
        permutation("", numbers, set);
        int count = 0;
        while(set.iterator().hasNext()){
            int a = set.iterator().next();
            set.remove(a);
            if(a==2) count++;
            if(a%2!=0 && isPrime(a)){
                count++;
            }
        }        
        return count;
    }

    public boolean isPrime(int n){
        if(n==0 || n==1) return false;
        for(int i=3; i<=(int)Math.sqrt(n); i+=2){
            if(n%i==0) return false;
        }
        return true;
    }

        public void permutation(String prefix, String str, HashSet<Integer> set) {
        int n = str.length();
        //if (n == 0) System.out.println(prefix);
        if(!prefix.equals("")) set.add(Integer.valueOf(prefix));
        for (int i = 0; i < n; i++)
          permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), set);

    }

}

---

👉🏻 4. 같은 유형 문제 (완전탐색)