프로그래머스 - 소수 찾기(c++, javascript)

문제 설명

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

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

 

제한사항

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

 

입출력 예

 

입출력 예 설명

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

 

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

출처

 

풀이

완전탐색 - 순열 문제

 

먼저 흩어진 종이 조각을 순서에 맞춰 놓는다고 했을 때 서로 다른 순서를 가지는 모든 경우의 수는 순열로 구할 수 있다.

순열은 라이브러리 함수(next_permutation)를 활용했고  (1개 ~ 종이 조각 개수) 만큼 선택하면서 얻을 수 있는 소수를 구해

중복이 안되게 set에 담았다.

 

set의 사이즈가 바로 만들 수 있는 총 소수의 개수! 

 

c++

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <math.h>
using namespace std;

int solution(string numbers) {
    int answer = 0;
    vector<int> v;
    set<int> s;
    
    for(int i=0; i<numbers.size(); i++){
        v.push_back(i);
    }
    
    int pick;
    do{
        pick = 0;
        while(pick < numbers.size()){
            ++pick;
            for(int i=0; i<numbers.size() - pick + 1; i++){
                string tmp = "";
                
                for(int j=0; j<pick; j++){
                    tmp += numbers[v[i+j]];
                }
                
                int num = stoi(tmp);
                bool isPrime = true;
                
                // 소수 구하기 (에라토스테네스의 접근)
                // 2부터 N의 제곱근까지의 수로 나눠서 나눠지는 수가 있으면 반복문 종료
                for (int i=2; i<=sqrt(num); i++) {
                    if (num % i == 0) {
                        isPrime = false;
                        break;
                    }
                }
                if(isPrime && num > 1) s.insert(num);
            }
            
        }
    }while( next_permutation(v.begin(), v.end()) );
    
    answer = s.size();
    return answer;
}

 

 

 

javascript

 

자바스크립트는 순열과 조합을 좀 더 공부해서 직접 함수로 구현해 풀어보려고 했는데

여기에 잘 나와 있어서 많은 도움이 되었다.

 

가장 핵심은 순열을 구하는 getPermutations 함수!

지금은 살짝 이해가 잘 가지 않는데 오늘은 늦었으니 내일 한번 천천히 봐야지 (yes~ 이해완료)

 

다음에 활용할 일이 있으면 그 때 c++로도 작성해보자

// 출처 : https://medium.com/@jun.choi.4928/javascript%EB%A1%9C-%EC%88%9C%EC%97%B4%EA%B3%BC-%EC%A1%B0%ED%95%A9-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-21df4b536349
const getPermutations= function (arr, selectNumber) {
  const results = [];
  if (selectNumber === 1) return arr.map((value) => [value]); // 1개씩 택할 때, 바로 모든 배열의 원소 return

  arr.forEach((fixed, index, origin) => {
    const rest = [...origin.slice(0, index), ...origin.slice(index+1)] // 해당하는 fixed를 제외한 나머지 배열 
    const permutations = getPermutations(rest, selectNumber - 1); // 나머지에 대해 순열을 구한다.
    const attached = permutations.map((permutation) => [fixed, ...permutation]); // 돌아온 순열에 대해 떼 놓은(fixed) 값 붙이기
    results.push(...attached); // 배열 spread syntax 로 모두다 push
  });

  return results; // 결과 담긴 results return
};

function solution(numbers) {
    var answer = 0;
    const arr = new Array(numbers.length).fill(0).map((ele,idx)=> numbers[idx]);
    const set = new Set();
    
    for(let i=1; i<=arr.length; i++){
    
    	// i 개의 순열을 구한다.
        const result = getPermutations(arr, i);
        
        // i 개의 순열을 순회하며
        result.forEach((ele)=>{
        
            // 문자열을 합쳐
            const num = parseInt(ele.join(""));
            let isPrime = true;
			
            // 소수인지 판별하고
            for (let i=2; i<=Math.sqrt(num); i++) {
                if (num % i == 0) {
                    isPrime = false;
                    break;
                }
            }
            
            // 소수가 맞다면 set에 추가한다.
            if(isPrime && num > 1) set.add(num);
        })
    }
    
    answer = set.size;
    return answer;
}

 

 

c++ 로 인덱스 쌍 조합을 만드는 함수를 만들어봤다.

// v : 인덱스를 담고 있는 배열
// selectNumber : 선택할 조합 개수.
vector<vector<int>> getCombinations(vector<int> v, int selectNumber) {
    vector<vector<int>> results;
    
    if (selectNumber == 1) {
        for(auto ele:v){
            vector<int> tmp(1, ele); // 재귀의 마지막 원소 선택
            results.push_back(tmp); 
        }
        return results;
    }
    
    for(int i=1; i<=v.size(); i++){
        int fixed = v[i-1]; // 고정 값
        vector<int> rest_v( v.begin()+i, v.end() );  // 나머지
        vector<vector<int>> combinations = getCombinations(rest_v, selectNumber - 1); // 고정 값을 뺀 나머지 원소에서 조합을 구한다.
        
        // 조합의 나머지 부분을 바로 앞의 고정값에 붙여나간다.
        for(int j=0; j<combinations.size(); j++){
            vector<int> tmp;
            tmp.push_back(fixed);
            for( int k=0; k<selectNumber; k++){
                tmp.push_back(combinations[j][k]);
            }
            results.push_back(tmp);
        }
    }

  return results;
}