문제

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

조건

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예시

numbers	return
"17"	3
"011"	2

통과한 풀이

아이디어

• 주어진 문자열에 들어있는 모든 숫자로 순열(Permutation)($_nP_r$)을 만들어내야 한다. 따라서, 이 문제에서는 순열을 구하는 함수를 구현하는 것이 제일 key point가 되겠다.
• 순열을 구하는 함수는 재귀함수로 구현한다.
  • r == 1일 때는 파라미터로 들어온 배열의 원소 하나하나에 대해서 배열로 만들어서 리턴해준다.
    ex) [1, 2, 3] => [[1], [2], [3]]
  • r >= 2일 때는 파라미터로 들어온 배열의 원소 하나하나에 대해서 fixed 수로 정해놓고, 나머지 원소들을 rest 배열에 모아놓은 다음, 그 rest를 가지고 다시 Permutation(rest, r-1)을 돌려 결과를 얻어낸다.
  • 위에서 얻어낸 결과의 모든 원소들과 fixed를 합쳐서 임시 결과로써 저장한다.
    코드적으로 설명하자면 temp_result = [fixed, ...permutation]
• 중복 제거를 위해서 JavaScript 내장 객체인 Set을 사용했다.

활용한 주요 메소드 / 문법

1. Array.prototype.forEach()와 Array.prototype.slice()의 조합
   forEach를 사용할 때는 콜백함수의 파라미터로 거의 currentvalue, index까지만 썼었었는데 이 문제에서는 array(원본배열)까지 활용하는 문제였다. 순열을 구하는 함수 내부에서 forEach()의 파라미터 array(원본배열)으로 slice() 메소드를 사용한다.

2. 스프레드 연산자
   Array.prototype.concat() 메소드를 사용하지 않고도 보다 간편하고 깔끔하게 두 배열을 병합시킬 때 사용한다. 순열을 구하는 함수 내부에서 유용하게 사용한다.

코드

// 소수 판별함수
function isPrime(n) {
    if(n < 2)
        return false;
    
    for(let i=2; i<=Math.sqrt(n); i++) {
        if(n % i === 0)
            return false;
    }
    return true;
}

// nPr만큼의 순열을 구하는 함수
function permutation(arr, r) {
    let temp_result = [];
    
    // Base case
    if(r == 1)
        return arr.map(n => [n]);
    
    // r이 2 이상일 떄
    arr.forEach((fixed, i, src) => {
        let rest = [...src.slice(0, i), ...src.slice(i+1)];
        let lowerLevel = permutation(rest, r-1);
        let attached = lowerLevel.map(elem => [fixed, ...elem]);
        temp_result.push(...attached);
    });
    
    return temp_result;
}

function solution(numbers) {
    let result = [];
    let numarr = numbers.split("");
    let set = new Set();
    
    for(let i=1; i<=numbers.length; i++) {
        let perm = [...permutation(numarr, i)];
        // console.log(perm);
        perm.forEach(p => {
            let testnum = ~~(p.join(""))
            if(isPrime(testnum))
                set.add(testnum);
        })
    }
    console.log(set);
    return set.size;
}

파이썬 버전

• itertools의 permutations를 사용하여 순열을 손쉽게 만든다. (하지만 그래도 데이터 처리는 필요함)
  • permutations 함수에 원하는 리스트와 길이를 넘겨주고 반환받은 값을 list() 함수를 이용하여 리스트로 바꿔준다.
  • 이때 리스트에 있는 원소들이 튜플 형식(ex. ("1", ))이므로, join 메서드를 통해 문자열 하나로 합쳐주고, 이를 int() 함수를 통해 숫자로 바꿔준다.
  • 그렇게 정상적인 숫자로 처리된 수들을 perm이라는 리스트에 저장하고, perm을 순회하면서 set에 넣어주어 중복된 수를 제거해준다.
  • 중복 제거된 수들을 is_prime 함수에 넣어 소수인지 판별되면 answer을 1씩 증가시키면 되는 로직이다.

import math
from itertools import permutations

def is_prime(number):
    if(number == 0 or number == 1):
        return False
    else:
        for i in range(2, int(math.sqrt(number)) + 1):
            if(number % i == 0):
                return False
    
    return True

def solution(numbers):
    numSet = set()
    nums = list(numbers)
    # 길이 1부터 numbers의 길이까지 순서대로 순열 돌린다
    for i in range (1, len(numbers) + 1):
        perm = [int("".join(tup)) for tup in list(permutations(nums, i))]
        # 만들어진 순열을 set에 넣어 중복을 제거한다.
        for n in perm:
            numSet.add(n)
    
    # 만들어진 set에 대해 하나하나 소수인지 판별한다.
    answer = 0
    for n in numSet:
        if(is_prime(n)):
            answer += 1
    
    return answer