[프로그래머스] 고득점 키트 - 완전탐색2

오늘 푼 문제

 

2. 소수찾기 / Lv.2 / 시간 : 91분(시간초과)

programmers.co.kr/learn/courses/30/lessons/42839?language=javascript

코딩테스트 연습 - 소수 찾기

1. 소수찾기(isPrime), 멱집합(getPowerSet), 순열(permutation) 이용

function solution(numbers) {
    var answer = 0;
    const configs = [];
    const checked = {};
    const numbersArr = numbers.split("");
    const len = numbers.length;
    
    const isPrime = (num)=>{
        if(num===0 || num ===1) return 0;
        for(let i=2; i<=Math.sqrt(num); i++){
            if(!(num%i)) return 0;
        }
        return 1; 
    };
    
    const getPowerSet = (k) =>{
      if(k===len){
          const tempSet = numbersArr.reduce((acc,cur,i)=>{
              if(configs[i]) acc.push(cur);
              return acc;
          },[]);
          let allSet = permutation(tempSet);
          
          let cnt = allSet.reduce((acc,cur)=>{
              const target = cur*1;
              if(!checked[target]) {
                  checked[target] = isPrime(target);
                  acc+=checked[target];
              }

              return acc;
          },0);
          
          
          answer+=cnt;
          
      }else{
          configs[k] = 0;
          getPowerSet(k+1);
          configs[k] = 1;
          getPowerSet(k+1);
      }
    };
    
    let permutation = (arr) => {
        return arr.reduce((acc,cur)=>{
            let temp1 = [];
            acc.forEach((subArr)=>{
                for(let i=subArr.length; i>=0; i--){
                    const temp2 = [...subArr]
                    temp2.splice(i,0,cur)
                    temp1.push(temp2.join(""))
                }
            });
            return temp1;
        },[""])
    }
    
    getPowerSet(0);
    
    return answer;
}

 

2. 소수찾기(isPrime), 순열(permutation) 이용.

멱집합대신 최대 조합에서 길이를 하나씩 줄여나가고, set을 이용해 중복을 제거하는 방식으로 전체 숫자 조합 생성.

function solution(numbers) {
    var answer = 0;
    const memoization = {};
    let numberArr = numbers.split("");
    
    const isPrime = (n) =>{
        if(n===0||n===1)return false;
        for(let i=2; i<=Math.sqrt(n); i++) if(!(n%i)) return false;
        return true;
    }
    
    let permutation = (arr) => {
        return arr.reduce((acc,cur)=>{
            let temp1 = [];
            acc.forEach((subArr)=>{
                for(let i=subArr.length; i>=0; i--){
                    const temp2 = [...subArr]
                    temp2.splice(i,0,cur)
                    temp1.push(temp2.join(""))
                }
            });
            return temp1;
        },[""])
    }
    
    let makeNumber = (arr) =>{
        let fullNumber = [...new Set(permutation(arr))];
        let numbers = [...fullNumber];
        
        for(let i=1; i<arr.length; i++){
            fullNumber = [...new Set(fullNumber.map(n=>n.slice(1)))];
            // numbers=[...numbers,...fullNumber];
            numbers=numbers.concat(fullNumber);
            // numbers.push(...fullNumber)
        }
        return numbers        
    }
    
    makeNumber(numberArr).forEach(number=>{
        number = number*1;
        if(memoization[number]===undefined){
            let result = isPrime(number);
            memoization[number] = result;
            if(result) answer++
        }
    })
       

    return answer;
}

 

 

1,2차 시간 비교 결과 :

파워셋을 사용해 멱집합을 만드는 것 보다, 이미 만들어진 순열을 잘라서 만드는게 더 빠르다.

1차 / 2차

 

---

노트

 

1. memoization

완전탐색 알고리즘 이지만 조금이라도 성능을 올리기 위해 memoization을 함께 사용함.

이미 탐색한 숫자에 대해서 isPrime을 다시 확인하지 않음

 

2. 배열 더하기 실험 (두 번째 풀이의 makeNumber 함수에서 numbers를 업데이트 하는 부분)

순서대로 스프레드 연산자 / concat / push 

결과 : concat의 성능이 가장 좋음

 

 

3. permutation 실험

 

1) 일반 반복문 사용

let permutation = (arr) =>{
    if(arr.length===1) return arr;
    else{
        let newArr = [];
        for(let i=0; i<arr.length; i++){
            let front = arr[i];
            let subArr = [...arr];
            subArr.splice(i,1);
            newArr.push(...permutation(subArr).map(n=>front+n))                
        }
        return newArr;
    }
}

 

2) reduce 사용

let permutation = (arr) => {
    return arr.reduce((acc,cur)=>{
        let temp1 = [];
        acc.forEach((subArr)=>{
            for(let i=subArr.length; i>=0; i--){
                const temp2 = [...subArr]
                temp2.splice(i,0,cur)
                temp1.push(temp2.join(""))
            }
        });
        return temp1;
    },[""])
}

 

일반 반복문 / reduce

결과 : reduce 사용하자