[Programmers 문제풀이 JAVA] Level 2 소수 찾기

 

📄 소수 찾기

🔗 문제 풀러가기

---

문제를 접근하는 방법은 2 가지가 존재 합니다. (더 많을 수도..)

• 첫 번째로, 숫자 조각으로 만들 수 있는 모든 숫자를 만들고 그 숫자들 중 소수의 개수를 세는 방법.
• 두 번째로, 숫자 조각으로 구할 수 있는 최대 수 까지 소수를 모두 구한 뒤 모든 소수를 검사하며 해당 소수가 숫자 조각들로 이루어 질 수 있는지 확인하는 방법

이 풀이에서는 두 번째 방법을 사용하여 문제를 해결하였습니다. 문제 풀이의 접근은 다음과 같습니다.

1. 숫자 조각들로 구할 수 있는 가장 큰 값을 구한다.
2. 가장 큰 값까지 소수를 구한다. (에라토스테네스의 체 이용)
3. 구해진 소수들 중 숫자 조각들로 만들 수 있는지 확인한다.

여기서 소수를 구하는 방법은 크게 문제가 되지 않습니다. 하지만 구해진 소수들이 숫자 조각들로 만들어질 수 있는가? 에 대하여 고민을 해야하는데 다음과 같이 생각할 수 있습니다. 주어지는 숫자는 0~9까지의 숫자로만 이루어져 있습니다. 따라서 주어진 숫자에서 사용할 수 있는 0~9의 개수를 세어 줍니다. 그 다음 소수에서 사용된 숫자 만큼 숫자의 개수를 줄여줍니다. 만약 소수에서 사용 된 수가, 사용할 수 있는 수보다 작다면 숫자 조각들로 만들 수 없는 소수입니다.

예를 들어, 주어진 수가 '123'이라고 가정했을 때 먼저 사용할 수 있는 0~9의 개수는 다음 표와 같습니다.

숫자	0	1	2	3	4	5	6	7	8	9
사용 가능 개수	0	1	1	1	0	0	0	0	0	0

다음 소수의 각자리 수를 확인하며 사용 가능 개수를 확인합니다.

소수 11을 만들 수 있는지 여부를 확인하면 소수 11은 1을 두 번 사용해야 하기 때문에 주어진 숫자 조각들로 만들 수 없는 소수입니다.
소수 2를 만들 수 있는지 여부를 확인하면 숫자 2를 한 번 사용할 수 있기 때문에 주어진 숫자 조각들로 만들 수 있는 소수 입니다.

 

글보단 소스코드를 보면 쉽게 이해할 수 있습니다.

 

---

🌱 Solution 함수

public int solution(String numbers) {
    int maxNum = makeMaxNum(numbers.toCharArray());
    boolean[] primeNum = findPrimeNum(maxNum);

    return findMakePossiblePrimeNum(primeNum, maxNum);
}

🌱 makeMaxNum 함수

주어진 숫자 조각들에서 구할 수 있는 가장 큰 값을 int형으로 반환합니다.

private int makeMaxNum(char[] inputNum) {
    Arrays.sort(inputNum);
    int len = inputNum.length;
    for (int i = 0; i < len/2; i++) {
        char temp = inputNum[i];
        inputNum[i] = inputNum[len - 1 - i];
        inputNum[len - 1 - i] = temp;
    }
    return Integer.parseInt(new String(inputNum));
}

🌱 findPrimeNum 함수

주어진 가장 큰 값까지의 소수를 에라토스테네스의 체를 이용하여 구합니다.

private boolean[] findPrimeNum(int maxNum) {
    boolean[] result = new boolean[maxNum + 1];
    for (int i = 2; i < Math.sqrt(maxNum); i++) {
        if (!result[i]) {
            for (int j = i * 2; j <= maxNum; j += i) {
                result[j] = true;
            }
        }
    }
    return result;
}

🌱 findMakePossiblePrimeNum 함수

주어진 숫자조각으로 만들 수 있는 소수들의 개수를 구하여 반환하는 함수입니다.

private int findMakePossiblePrimeNum(boolean[] primeNum, int maxNum) {
    int possiblePrimeNumCount = 0;

    for (int primeNumIndex = 2; primeNumIndex <= maxNum; primeNumIndex++) {
        if (!primeNum[primeNumIndex] && isPossible(maxNum, primeNumIndex)) {
            possiblePrimeNumCount++;
        }
    }
    return possiblePrimeNumCount;
}

🌱 isPossible 함수

해당 소수가 주어진 숫자 조각으로 만들어질 수 있는지 여부를 판단하는 함수입니다.

private boolean isPossible(int maxNum, int primeNum) {
    int[] numCount = countAvailableNums(maxNum);

    while(primeNum != 0) {
        if (numCount[primeNum % 10] <= 0) return false;
        numCount[primeNum % 10]--;
        primeNum /= 10;
    }

    return true;
}

🌱 countAvailableNums 함수

주어진 숫자조각에서 사용할 수 있는 0~9의 개수를 세는 함수입니다.

private int[] countAvailableNums(int maxNum) {
    char[] str = String.valueOf(maxNum).toCharArray();
    int[] numCount = new int[10];
    for (int i = 0; i < str.length; i++) {
        numCount[str[i] - '0']++;
    }
    return numCount;
}

---

💡 Github에 더 많은 문제 풀이가 있습니다.

Programmers 문제 풀이

BaekJoon Online Judge 문제 풀이