[알고리즘] 여러 원리를 함께 적용하기 (레벨2 소수찾기)

문제

기록

• 알고리즘에선 경우의 수 문제가 많다. 그 중에 단골로 등장하는 문제가 바로 줄세우기(혹은 뽑아서 줄세우기)인데, 순열 조합이라고 부르기도 한다.

• 순열의 경우의 수를 구하는 것은 수학적인 개념을 적용하면 되지만, 그 case들을 나열하는 것이면 얘기가 달라진다. 재귀함수를 이용하여 원하는 데이터로 나열해야 하기 때문. 재귀함수를 사용하는 것 자체가 비효율적인 부분이 있어서 최적화 하는데에 항상 스트레스.

• 여태까지 순열 조합에 시달리며 재귀함수를 이것저것 짜봤는데, 역시나 재귀함수 자체는 결과를 위한 최적화된 코드는 짤 수 없다. 매 함수 컨텍스트 마다 원하는 모양을 만들기 위해 불필요하게 반복되는 코드가 존재할 수밖에 없기 때문이다. 그럼에도 재귀함수를 쓸수 밖에 없는 이유는 재귀함수밖에 구현하지 못하기 때문?

  (예를들어 순열을 만들기 위해 기준을 잡고 순서를 바꾸는 방식이든, 맨앞으로 넘기는 방식이든, 잘랐다가 다시 붙히는 방식이든 배열을 fasly 값으로 바꿔주는 방식이든 고정된 수를 잡고 나머지 순서를 바꾸는 단계에서 한 번 이상 필요없는 코드를 반복하는 것을 피할 수 없다. 어쩌면 내 머리의 한계일지도..?)

내 답

function solution(numbers) {
  	let result = [];
  	let numbersArr = numbers.split('').sort((a,b)=>a-b)
  	const getPermutations = (arr,str) => {
    	for (let i = 0 ; i<arr.length; i++){
      		let temp = arr.slice();
      		let tempStr = str;
          	if(temp[i] !== null){
            	tempStr += temp[i];
            	result.push(Number(tempStr))
            	temp[i] = null;
            	getPermutations(temp,tempStr)
          	}
        }
    }
    
    getPermutations(numbersArr, '')
  
  	let max = Math.sqrt(result[result.length-1])

	for(let i = 2; i<=max; i++){
  		for(let j = 0; j<result.length; j++){
    		if(result[j] !== null){
      			result[j] === 1 ? result[j] = null : null;
      			result[j] % i === 0 && result[j] / i !== 1 ?  result[j] = null : null; 
    			}
  		}
	}

	return result.filter((el,i)=> el && i === result.indexOf(el)).length; 
}

풀이

• 해당 문제는 단순 nPr의 순열문제가 아니라 nP1 + nP2 + ... + nPn 의 경우들을 모두 나열 한 후 그중 소수가 몇개냐 하는 문제다.
• 앞에서부터 하나씩 조합해나가는 방식의 순열을 만든다. 애초에 내가 문제에서 필요한 건 string으로 조합된 숫자이기 때문에 string을 재귀함수의 인자로 만들었다.

const getPermutations = (arr,str) => {
  
  
  for (let i = 0 ; i<arr.length; i++){
    let temp = arr.slice();
    let tempStr = str;
    if(temp[i] !== null){
      tempStr += temp[i];
      
      console.log(Number(tempStr))//조합될때마다 출력
      
      temp[i] = null;
      getPermutations(temp,tempStr)  
    }
  }
}
getPermutations([0,1,2], '') 
//console : '0' '1' '12' '2' '21' '1' '10 ... Number()에 의해 앞에 0은 제거된다.

• 이제 소수를 구해야하는데, 구할 수 있는 방법을 세가지로 나눴다.

1. 각각 나온 수들을 증감식으로 나누며 나눠지는 수들이 있는지 검사하는 방법. 이 방법은 직관적이지만 역시나 조합된 수마다 이중으로 반복문을 거쳐야 하기 때문에 비효율적이다. Pass~

function solution(n){
  let result = 0;
  for(let i = 2; i<=n; i++){
    let count = 0;
    for(let j = 2; j<=i; j++){
      if(i % j === 0) count++
    }
    count === 1 ? result ++ : null;
  }
  return result;
}

2. 1)의 방법을 배열에 담아 한꺼번에 걸러내는 법. (아라토스테네스의 체와 비슷)
   Math.sqrt(조합될 수 있는 최대값) 까지만 배수를 검사해도 된다. 자세한 설명은 여기

function solution(numbers) {
    let result = [];
    let numbersArr = numbers.split('').sort((a,b)=>a-b)

const getPermutations = (arr,str) => {


  for (let i = 0 ; i<arr.length; i++){
    let temp = arr.slice();
    let tempStr = str;
    if(temp[i] !== null){
      tempStr += temp[i];
      result.push(Number(tempStr))
      temp[i] = null;
      getPermutations(temp,tempStr)
    }
  }
}

getPermutations(numbersArr, '')

let max = Math.sqrt(result[result.length-1])

for(let i = 2; i<=max; i++){
  for(let j = 0; j<result.length; j++){
    if(result[j] !== null){
      result[j] === 1 ? result[j] = null : null;
      result[j] % i === 0 && result[j] / i !== 1 ?  result[j] = null : null; 
    }
  }
}

return result.filter((el,i)=> el && i === result.indexOf(el)).length; 
  //0이 포함되었을때 중복될 값도 제거해줘야한다. 
}

3. 아라토스테네스의 체

function solution(numbers) {
    
    let numbersArr = numbers.split('').sort((a,b)=>b-a)
    const filterArr = new Array(Number(numbersArr.join(''))+1);
    filterArr.fill(1)
    
    
    const getPermutations = (arr,str) => {
  
  
  for (let i = 0 ; i<arr.length; i++){
    let temp = arr.slice();
    let tempStr = str;
    if(temp[i] !== null){
      tempStr += temp[i];
      filterArr[Number(tempStr)] = 2;
      temp[i] = null;
      getPermutations(temp,tempStr)
    }
  }
}

getPermutations(numbersArr, '')

let max = Math.sqrt(numbersArr.join(''))
filterArr.fill(0,0,2)

for(let i= 2; i<=max; i++){
    if(filterArr[i]){
      for(let j = i * 2; j<filterArr.length; j+=i){
        filterArr[j]= 0; 
      }
    }
  }
    return filterArr.filter(el=>el && el === 2).length;
}

4. 효율성 비교. 위가 2번 아래가 3번의 방법이다. 체를 직접적으로 구현하는 방법은 조금 더 비효율적인 결과가 나왔다. 이는 계산없이 바로 할당을 하며 순회하는 체의 방법이 매 인덱스마다는 처리가 빠르긴 하지만 몇개의 소수를 걸러내기 위해 필요없이 긴 길이의 배열을 만들어야하며, 그 중간 인덱스를 다 거쳐가야하는게 비효율적이기 때문이다. 이럴 경우는 단순히 필요한 숫자들로만 배열을 만들어 걸러내는게 더 효율적!

		위가 2번, 아래가 3번이다.