(C++, Javascript) - 프로그래머스(Summer/Winter Coding(~2018)) : 소수만들기

programmers.co.kr/learn/courses/30/lessons/12977

코딩테스트 연습 - 소수 만들기

소수 판별, 조합 구현 문제였습니다.

 

풀이방법

 1. 3개의 수를 조합(순서 상관 O)으로 뽑은 후 세 수를 더한 값을 구합니다.

 2. 해당 값으로 미리 1만까지의 자연수에 대한 소수여부를 판별한 배열과 대조해 소수여부를 판별합니다 : 에라토스테네스의 체 (시간복잡도 O(N루트N))

Code

C++

#include <vector>
#include <iostream>
using namespace std;

int prime[10000];
int ck[10000];
int threeNums[3];
int answer = 0;

void initPrime(){
    prime[0] = 1;
    prime[1] = 1;
    for(int i = 2; i*i <= 10000; i++){
        for(int j = i+i; j<=10000; j+=i){
            if(!prime[j]) prime[j] = 1;
        }
    }    
}

bool isPrime(int primeNum){
    if(prime[primeNum]) return 0;
    else return 1;
}

void backtracking(vector <int> &nums,int level,int idx){
    if(level==3){
        int primeNum = 0;
        for(int i = 0; i < 3; i++) primeNum += threeNums[i];
        if(isPrime(primeNum)) 
            answer++;
        return;
    }
    for(int i = idx; i < nums.size(); i++){
        if(!ck[nums[i]]){
            ck[nums[i]] = 1;
            threeNums[level] = nums[i];
            backtracking(nums,level+1,i);
            ck[nums[i]] = 0;
        }
    }
    return;
}

int solution(vector<int> nums) {
    initPrime();
    backtracking(nums,0,0);
    return answer;
}

 

Javascript

let comb = [];
let num = [];
let ck = Array.from({ length: 50 }, (undefined, i) => 0);
let primeCk = Array.from({ length: 100001 }, (undefined, i) => 0);
let answer = 0;
function makePrime() {
  for (let i = 2; i <= 100000; i++) {
    if (primeCk[i] == 0) {
      for (let j = i + i; j <= 100000; j += i) primeCk[j] = 1;
    }
  }
}
makePrime();

function dfs(depth, idx) {
  if (depth === 3) {
    let sum = 0;
    for (let i = 0; i < comb.length; i++) sum += comb[i];
    if (primeCk[sum] === 0) answer++;
    return;
  }
  for (let i = idx; i < num.length; i++) {
    if (ck[i]) continue;
    ck[i] = 1;
    comb.push(num[i]);
    dfs(depth + 1, i + 1);
    comb.pop();
    ck[i] = 0;
  }
}
function solution(nums) {
  num = nums;
  answer = 0;
  dfs(0, 0);
  return answer;
}