[JS] 프로그래머스 - 소수찾기(완전탐색 )

문제 설명

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

나의 풀이

function solution(numbers) {
    let answer = 0;
    let arr = numbers.split("");
    let k = 1;
    let i = 0;
    let store = [];

    arr = permutation(arr);

	// 배열의 원소를 한 자리부터 n자리 까지 잘라서 정수로 변환 뒤에 store에 push
    for(let i=0; i<arr.length; i++){
      let j = 1;
      while(j<=arr.length){
        const num = arr[i].slice(0,j)/1;
        //중복 체크
        if(num > 1 && !store.includes(num))
          store.push(num);
        j++;
      }
    }

	// 오름차순 정렬
    store.sort((a,b) => a-b);

	// 소수 판별
    answer = primeCheck(store);

    return answer;
}

function primeCheck(arr){
  let count = 0;

  for(let i=0; i<arr.length; i++){
    let check = true;
    for(let j=2; j*j<=arr[i]; j++){

      if(arr[i]%j===0){
        check = false;
        break;
      }     
    }

    if(check){
      count++;
    }
  }

  return count;
}

function permutation(arr,store=[],idx=0){
  const str = arr.join("");

  if(idx === arr.length-1){
      store.push(str);
    return;
  }

  for(let i=idx; i<arr.length; i++){
    let temp = arr[idx];
    arr[idx] = arr[i];
    arr[i] = temp;

    permutation(arr, store, idx+1);

    arr[i]= arr[idx];
    arr[idx] = temp;
  }
    
    return store;
}

 

이틀 간의 대장정 끝에 겨우 푼 문제이다. 레벨 2인데 쩔쩔매다니.. 아직 많이 멀었다...

 

나는 네 가지를 이용하여 문제를 풀 수 있었다.

1. 순열(순열에 대해서는 이 문제를 풀기전에 한번 포스팅을 했었다(순열[이전 포스트 글]).)

2. 0, 1을 제외하고 1자리에서 n자리까지의 자연수를 중복없이 만듦.

(입력: "011"일 경우 -> [10, 11, 101, 110]으로 만들어야 한다.]

3. 중복 제거 후 정렬(오름차순)

4. 소수 체크(정확히는 약수 개수 확인)

 

 

순열을 이용해야한다는 것은 알겠으나, 아직도 재귀함수의 원리 및 순서를 잘 모르기 때문에 많이 헤맸다.

또한 , 소수를 체크하는 과정을 에라토스테네스의 체(위키백과)를 이용하여 문제를 해결하려 했으나,

실패(시간 초과)의 남발로 멘붕... 첫 날은 그대로 포기했다.

 

 

둘 째날, 무엇이 잘못됐는지 확인해보니,

이 문제의 목적은 소수를 체크하는 것이다. 하지만 내 코드는 2에서 입력받은 수까지의 소수 개수를 구하는 것이니

당연히 시간초과가 뜰수 밖에...

 

 

그래서 에라토스테네스의 체를 지워버리고

입력받은 수의 1과 자신 이외의 약수 유무를 판단하는 함수를 만들어서 소수를 체크할 수 있었다.

 

 

순열 함수의 동작 순서

이것을 쓰는 목적은 재귀 순서를 좀 더 이해하기 위해서이다.

확실히 알면 그냥 보지 않아도 된다.

 

 입력받은 문자열 "011"을 배열로 바꿔준다.

 

[그림 1] 문자열 "011"을 배열 [0, 1, 1]로 변환 

 

 [0, 1, 1]의 원소는 0, 1, 1이다. 이 세 개의 원소의 자리를 바꿔서 밑의 그림과 같이 서로 다른 세 자리 숫자를 만들어 줘야한다. 

원소의 중복이 없으면, 독립적인 세 자리수 6개를 만들 수 있지만, 원소 1의 중복으로 독립적인 세 자리 숫자 6개를 만들 수 없다.

따라서 나는 순열과 중복을 없애는 작업을 따로 만들었다.

 

[그림 2] 순열 알고리즘을 이용하면 6개(주황색이 2개 칠해져 있는 것의 수)를 얻어야한다.

 

순열 알고리즘 동작도

내가 짠 순열 알고리즘의 순서도는 다음과 같다.

[그림 3] permutation 순서도(정확한지는 모르겠다)

 

 순열 알고리즘은 재귀함수를 이용한다. 재귀함수는 스택구조를 가지고 있다. 재귀함수를 이용하여 팩토리얼을 구현할 경우, 데이터 흐름도를 쉽게 파악할 수 있었지만, 순열은 어려웠다. 나는 순열의 데이터 흐름도를 파악하기 위해 출력함수를 이용하여 분석했다. 그 결과 나는 "011"을 입력받을 때 크게 세 가지 과정이 있다는 것을 알 수 있었다. 

 

 

 1. [0, 1, 1](idx=1)의 데이터를 스택(재귀함수)에 먼저 넣는다.
 2. [0, 1, 1](idx=1)을 스왑하면 [0, 1, 1]이 두 개가 나온다. [0, 1, 1](idx=2), [0, 1, 1](idx=2)을 각각 스택에 넣는다.

 3, 4. [0, 1, 1](idx=2)을 꺼내서 store배열에 넣고 store를 리턴한다.
 5. [0, 1, 1](idx=1)을 꺼낸다.

  나머지도 같은 작업을 거친다.

 

 1. [1, 0, 1](idx=1)의 데이터를 스택(재귀함수)에 먼저 넣는다.
 2. [1, 0, 1](idx=1)을 스왑하면 [1, 0, 1], [1, 1, 0]이 나온다. [1, 0, 1](idx=2), [1, 1, 0](idx=2)을 스택에 넣는다.

 3, [1, 1, 0](idx=2)을 꺼내서 store배열에 넣고 store를 리턴한다.
 4. [1, 0, 1](idx=2)을 꺼내서 store배열에 넣고 store를 리턴한다.
 5. [1, 0, 1](idx=1)을 꺼낸다.

 

 

 1. [1, 1, 0](idx=1)의 데이터를 스택(재귀함수)에 먼저 넣는다.
 2. [1, 1, 0](idx=1)을 스왑하면 [1, 1, 0], [1, 0, 1]이 나온다. [1, 1, 0](idx=2), [1, 0, 1](idx=2)을 스택에 넣는다.

 3, [1, 1, 0](idx=2)을 꺼내서 store배열에 넣고 store를 리턴한다.
 4. [1, 0, 1](idx=2)을 꺼내서 store배열에 넣고 store를 리턴한다.
 5. [1, 1, 0](idx=1)을 꺼낸다.

 

  

  따라서 순열함수를 최종적으로 리턴하면 [011, 011, 110, 101, 101, 110]이 나온다.

 

참고자료

1. 자바스크립트 취준생 이야기 - [JS] 순열

2. not yet a Developer - 약수 알고리즘(Division Algorithm)