프로그래머스 - 소수찾기

프로그래머스 - 소수찾기

문제 접근 방법

주어진 문자열(숫자로만 구성된)로 생성가능한 모든 종류의 조합(순서를 고려한)을 구한다.
그 조합중 가장 큰 수를 찾는다.
가장 큰 수까지의 소수리스트를 생성한다.
모든 조합을 순회하며 소수인지 확인한다.

prime_num_list생성

n까지의 prime_num_list를 생성한다.
단 생성 규칙을 다음과 같이 정한다.

1. 각 index의 위치는 해당하는 정수를 의미한다.
2. 해당 숫자가 소수인지는 Boolean값으로 나타낸다.
   ex) 숫자 5는 소수인가 -> prime_num_list[5] -> true

모든 조합 생성

주어진 문자열에 대해 1개씩 선택하는 모든 조합부터
문자열의 길이만큼 선택하는 조합까지를 전부 담고있는 리스트를 생성한다.(선택하는 순서를 고려한다.)
단, '011'과 '011'은 선택하는 순서가 다르지만 동일한 숫자로 표기될 수 있으므로 이경우에는 하나로 간주한다.

완성한 솔루션

JavaScript

function solution(numbers) {
    // 주어진 문자열의 모든 조합을 구한다.
    let allCombination = combination(numbers);
    // 그중 제일 큰 수를 찾는다.
    let maxNum = Math.max(...allCombination);
    // 제일 큰 수까지의 소수들을 갖는 배열을 만든다.
    let primeNumList = makePrimeNumList(maxNum);
    // 구했던 조합 중 소수의 개수를 확인한다.
    return allCombination.filter((val) => primeNumList[val]).length;
}

function makePrimeNumList(n) {
    // 길이가 n + 1인 true로 채워진 Array를 만든다.
    let temp = Array(n+1).fill(true);
    let min = Math.floor(n ** 0.5); // n의 제곱근을 정수부만 취함.

    // min까지만 반복하는 이유는
    // n의 제곱근 ~ n 사이의 수가 제곱되면 n을 초과하기에 검증할 필요가 없음.
    // 2배 ~ 제곱이기 직전 배수는 직전까지의 검증에서 걸러진다.
    for (let i = 2; i <= min; i++) {
        if (!temp[i]) continue; // 이미 false라면 다음으로
        for (let j  = i * 2;j <= n;j += i) {
            temp[j] = false; // i는 소수이지만 i의 모든 배수는 소수가 아님.
        }
    }
    temp[0] = temp[1] = false; // 0과 1은 소수가 아니다.
    return temp;
}

// 주어진 문자열에서 등장 가능한 모든 숫자조합
function combination(word_n) { // word_n: 숫자로 이루어진 문자열
    let temp = [];
    for (let i = 1; i <= word_n.length; i++) {
        temp.push(...helper(word_n, i));
    }
    temp = new Set(temp.map((val) => parseInt(val)));
    return [...temp];
}

function helper(word, num) { // 문자열에서 num개 선택하는 (순서를 고려하여) 조합.
    let temp = [];
    if (num === 1) return [...word];
    else if (word.length < num) return [];
    for (let i = 0; i < word.length; i++) {
        temp.push(...helper(word.slice(0, i) + word.slice(i + 1), num - 1)
                  .map((val) => word[i] + val));
    }
    return temp;
}

Python3

def solution(numbers):
    all_combi = all_combination(numbers)
    prime_num_list = make_prime_num_list(max(all_combi))
    return len([True for i in range(len(all_combi)) if prime_num_list[all_combi[i]]])

def combination(word, num):
    if num == 1: return [*word]
    elif len(word) < num: return []
    temp = []
    for i in range(len(word)):
        temp += [word[i] + j for j in combination((word[0:i] + word[i + 1:]), num - 1)]
    return temp

def all_combination(word):
    temp = set()
    for i in range(len(word)):
        for j in combination(word, i + 1): temp.add(int(j))
    return list(temp)


def make_prime_num_list(max_num):
    prime_num_list = [True for i in range(max_num + 1)]
    min_num = int(max_num ** 0.5)
    for i in range(2, min_num + 1):
        if not prime_num_list[i]: continue
        for j in range(i * 2, max_num + 1, i): prime_num_list[j] = False
    prime_num_list[0] = prime_num_list[1] = False
    return prime_num_list

문자열의 모든 조합을 생성하는 함수

문자열의 모든 조합을 생성하는 함수는
문자열에서 n개만큼 선택하는 조합을 생성하는 함수를
1부터 문자열의 길이만큼 호출하여 리스트(배열)에 저장하도록 한다.

문자열에서 n개만큼 선택하는 조합을 생성하는 함수

직관적이고 작성하기 용이한 recursion(재귀함수)으로 디자인 하였다.
1개씩 선택하는 조합일 경우 받은 문자열을 spread_operator로 리스트를 생성한다.

1개 이상일 경우 각 문자열을 순회하며 재귀호출 한다.
이때, (자신을 제외한 문자열, 조합하려는 수 - 1)로 호출한다.
그 반환되는 값(리스트)에 대하여, 모든 요소 앞에 자신을 삽입한다.

n까지의 소수 집합을 생성하는 함수

소수: 1과 자기 자신으로만 나눌 수 있는 숫자.

어느 한 숫자가 소수인지 판단하려면 2부터 자신의 제곱근까지(소수부 버림)
자신을 나눌 수 있는 수가 존재하는지 확인하면 된다.
하지만 소수인지 판별해야 할 수가 다수 존재하는 상황에서
모든 수를 위 방법대로 확인하기엔 비효율적일것 이다.

그래서 주어진 n까지의 모든 소수를 담은 리스트를 생성하기로 생각했다.
한번 생성해놓으면 중복된 계산없이 진행할 수 있다.
게다가, 소수의 특성을 이용하여 이전 소수에 대한 정보가 있다면
다음 소수를 찾기 용이하다.

1. 1이 아닌 모든 수의 배수는 소수가 아니다.
2. 소수의 배수도 소수가 아니다.
3. 현재 숫자가 진행중에 등장한 모든 소수의 배수가 아니라면
   이 숫자는 소수이다.

• 즉, 에라토스테네스의 체 기법을 사용한다.

모든 요소가 true로 구성된 리스트를 n번째 index(길이로 치면 n + 1개)까지 생성한다.
각 index번호는 해당번호의 숫자(정수)를 취하게 하여 계산 및 소수 여부 접근에 용이하게 한다.
0과 1은 소수가 아니기에 2부터 시작하여 n의 제곱근(소수부 버림)을 포함하는 수 까지 반복한다.

사전에 구성한 리스트에 해당 index로 접근하여 값이 true라면 그 숫자는 소수라는 뜻이며,
이 숫자의 모든 배수는 소수가 아니기에 이 숫자의 배수로 구성된 모든 index의 값을 false로 변경한다.
ex) list의 길이: 11일때, list[2]: true -> list[4], list[6], ..., list[10] = false
접근했을때 값이 false라면 그 숫자는 소수가 아님을 의미하므로 아무것도 계산할 필요가 없다.

계산이 완료되면 0번, 1번째 index를 false로 변경한다.
반환된 리스트는 각 인덱스에 해당하는 숫자의 소수 여부가 Boolean값으로 담겨있다.
ex) 숫자 7은 소수인가 -> list[7]: True -> 소수이다.

아쉬운점

이미 에라토스테네스의 체를 이용하여 소수를 찾아본 경험이 있다.
그래서 조금 쉽게 문제를 해결할 수 있었던 것 같다.

이미 효율성이 높은 방법을 알고 있어도 한번 더 다른 고효율의 방식을
탐구해보는것도 좋을것 같다.
(물론 어떤 문제를 해결함에 있어 고효율 해결방법의 탐구에 너무 매진하면 주객이 전도되니... 적당히..!)

---

수정)
본문에 빠진 내용이 존재하는데
모든 조합을 돌려받을때 바로 접근하여 사용하기 위하여
각 요소들을 모두 정수로 형변환 시켜주었으며
Set를 사용하여 중복을 제거하였습니다.