모각코PS / 프로그래머스 Lv2 소수 찾기

모각코 PS스터디

이번주 마지막 문제는 소수 찾기였습니다. 문제는 간단합니다. 문자열로 주어진 숫자열이 있고, 숫자들을 한번 or 0번 써서 만들어낼 수 있는 숫자들을 모읍니다. 그리고 그 숫자가 소수(prime number)라면 체크합니다. 총 체크된 수를 리턴합니다.
말 그대로 구현했는데요, 한번 같이 보시죠.

문제와 풀이

---

문제 링크 : 프로그래머스 Lv2 소수 찾기
이 문제의 원 출처 : nwerc.eu 09년도 아카이브

👇펼쳐서 코드와 해설 읽기

로직의 흐름은 이렇습니다.

일단 걸러낼 정보를 거릅니다. 저는 길이가 0인 경우 || 0을 전부 공백으로 치환했을 때 길이가 0이 되는 경우 || 그리고 문자열이 "1"인 경우를 걸렀습니다.
지금 말하면서 보니 길이가 0인 경우는 따로 체크하지 않아도 되겠네요(두번째 조건에서 함께 걸림).

그리고 Set을 하나 만듭니다. 숫자조합들을 담을 집합입니다. 조합한 숫자의 순서를 보장할 것("123"과 "213"은 다른 숫자로 판단)이기 때문에, 조합(Combination)이 아니라 순열(Permutation)으로 접근해야겠죠?
재귀로 구현(permutation())한 순열의 결과를 위 Set(permSet)에 담습니다.

permSet을 차례로 돌며 소수인지 판별(isPrime())합니다. 소수면 카운팅합니다.

결과를 리턴하여 마칩니다.

import java.util.*;

class Solution {
    public static void main(String[] args) {

        Week3_1 w = new Week3_1();
        System.out.println(w.solution("0003"));

    }

    public int solution(String numbers) {
        if (numbers.length() == 0
                || numbers.replace("0", "").length() == 0
                || numbers.equals("1")) {
            return 0;
        }

        Set<Integer> permSet = new HashSet<Integer>();
        permutation("", numbers, permSet);

        int countPrime = 0;
        for (Integer num : permSet) {
            if (isPrime(num)) {
                countPrime++;
            }
        }

        return countPrime;
    }

    private boolean isPrime(int n) {
        if (n == 0 || n == 1) {
            return false;
        }
        for (int i = 2; i < n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    private void permutation(String prefix, String str, Set<Integer> store) {
        if (!prefix.equals("")) {
            store.add(Integer.valueOf(prefix));
        }
        for (int i = 0; i < str.length(); i++) {
            permutation(prefix + str.charAt(i),
                    str.substring(0, i) + str.substring(i + 1),
                    store);
        }
    }
}

마무리

---

소수인지 판단하기 위한 방법으로 곧장 '에라토스테네스의 체'가 떠올라서, 처음에는 그렇게 구현했었습니다.
그런데 생각을 해보니, 꼭 그게 필요할까 싶었습니다.

소수 판별을 위해서 n자릿수의 배열을 메모리에 올려놓는게 좋은 방식일까?

n자릿수의 숫자까지 소수를 모두 구해야 한다면 당연히 에라토스테네스의 체가 효율적이겠지만, 단순히 n자릿수의 숫자가 소수인지 판별하는 문제라면 그냥 전통적인 소수확인법(1과 자신으로만 나눠떨어지는지 확인)이 빠를 거란 생각이 들어 수정했습니다.

그리고 위의 코드에서는 수정하지 않았지만, isPrime() 메서드 내부의 for문에서 짝수는 미리 걸러내는 것이 좋겠다는 생각이 들었습니다. 루프 횟수를 n/2번으로 줄일 수 있을테니까요.

조합과 순열에 대해서는 고등학교 이후로 생각해본 적이 없는데, 이 문제를 풀면서 오랜만에 떠올렸습니다.
다시 익숙해질 필요가 있겠다는 생각이 들었습니다.

수정하고싶은 코드가 많지만, 컨디션이 좋지 않아 적당히 마쳤습니다.

소감 끝!