회사에 코딩 관련 동호회가 만들어져 신규 회원을 모집하면서 알고리즘 문제를 냈는데 딱히 알고리즘 문제를 풀어본 적은 없지만 문제를 보니 해볼만 하겠다 싶어경품 중 하나인 에어팟 무선 충전 케이스가 갖고 싶어서 참여해보게 됐다.

소수 찾기

문제 설명

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

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

제한사항

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

입출력 예

“17” 3
“011” 2

입출력 예 설명

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

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

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

제출코드

아래 코드가 제출코드인데 언어 사용에 제한은 없었지만 제일 능숙한 자바스크립트 웹환경에서 했고 집에서 할때는 재귀함수 형태로 구현했는데 회사에서 해보니 자릿수가 6자리 이상되면 무한 재귀 호출 오류Maximum call stack size exceeded가 발생해 부랴부랴 수정해서 제출했다.

제출코드 - 반복문 형태

function solution(numbers) {
  if (typeof numbers !== 'string' || numbers.length < 1 || numbers.length > 7) {
    return;
  }

  var arr = [numbers.split('')]; // 모든 경우의 조합을 담을 배열
  var pointer = 0; // 모든 경우의 조합을 담을 때 필요한 앞자리수의 위치
  var depth = arr.length; // 모든 경우의 조합을 담을 때 필요한 자리수
  var source = []; // 중복방지를 위한 어떤 앞자리에서 가져왔는지 출처를 담아놓을 배열
  var list = []; // 모든 경우의 조합을 하나의 배열로 담기 위한 배열
  var checkList = []; // 조건에 맞는 값만 담을 배열

  // 나올 수 있는 모든 조합 구하는 반복문
  var combi = function() {
    while (pointer < arr[depth - 1].length) {
      arr[depth] = arr[depth] || [];
      source[depth] = source[depth] || [];

      for (var i = 0; i < arr[0].length; i++) {
        if (source[depth - 1]) {
          if (source[depth - 1][pointer].includes(i)) {
            continue;
          }
        } else {
          if (pointer === i) {
            continue;
          }
        }

        arr[depth].push(arr[depth - 1][pointer] + arr[0][i]);

        if (source[depth - 1]) {
          source[depth].push(source[depth - 1][pointer].concat(i));
        } else {
          source[depth].push([pointer, i]);
        }
      }

      pointer++;
    }

    depth++;
    pointer = 0;
  };

  // 소수 판별
  var checkNumber = function(number) {
    number = Number(number);

    if (number === 2) {
      return true;
    }

    if (number < 2 || number % 2 === 0) {
      return false;
    }

    for (var i = 3; i < number; i+=2) {
      if (number % i === 0) {
        return false;
      }
    }

    return true;
  };

  // 나올 수 있는 모든 조합 구하기 실행
  do {
    combi();
  } while(depth < arr[0].length);

  // 위에 구한 모든 조합을 한 배열에 몰아넣기
  for (var i = 0; i < arr.length; i++) {
    list = list.concat(arr[i]);
  }

  // 앞자리가 0이면 거르고, 소수 체크하여 해당되는 숫자 담기
  for (i = 0; i < list.length; i++) {
    if (list[i][0] == 0) {
      continue;
    }

    if (checkNumber(list[i]) && !checkList.includes(list[i])) {
      checkList.push(list[i]);
    }
  }

  // 조건에 맞는 배열이 몇갠지 반환
  return checkList.length;
}

console.log(solution('17'));
console.log(solution('011'));

아래 코드가 무한 재귀 호출 오류가 발생하는 원코드..

제출코드 - 재귀함수 형태

function solution(numbers) {
  if (typeof numbers !== 'string' || numbers.length < 1 || numbers.length > 7) {
    return;
  }

  var checkNumber = function(number) {
    number = Number(number);

    if (number === 2) {
      return true;
    }

    if (number < 2 || number % 2 === 0) {
      return false;
    }

    for (var i = 3; i < number; i+=2) {
      if (number % i === 0) {
        return false;
      }
    }

    return true;
  };

  var combination = function(arr = [numbers.split('')], pointer = 0, depth = 1, source = []) {
    arr[depth] = arr[depth] || [];
    source[depth] = source[depth] || [];

    if (pointer < arr[depth - 1].length) {
      for (var i = 0; i < arr[0].length; i++) {
        if (source[depth - 1]) {
          if (source[depth - 1][pointer].includes(i)) {
            continue;
          }
        } else {
          if (pointer === i) {
            continue;
          }
        }

        arr[depth].push(arr[depth - 1][pointer] + arr[0][i]);

        if (source[depth - 1]) {
          source[depth].push(source[depth - 1][pointer].concat(i));
        } else {
          source[depth].push([pointer, i]);
        }
      }

      pointer++;
    } else {
      depth++;
      pointer = 0;
    }

    if (depth < arr[0].length) {
      combination(arr, pointer, depth, source);
    }

    return arr;
  };

  var arr = combination();

  var list = [];
  var checkList = [];

  for (var i = 0; i < arr.length; i++) {
    list = list.concat(arr[i]);
  }

  for (var i = 0; i < list.length; i++) {
    if (list[i][0] == 0) {
      continue;
    }

    if (checkNumber(list[i]) && !checkList.includes(list[i])) {
      checkList.push(list[i]);
    }
  }

  return checkList;
}

console.log('result', solution('017'));

첫번째의 코드는 마감시간이 다 되어가 어쩔 수 없이 재귀함수를 반복문으로 바꿔 풀어쓴 형태라 아쉬움이 좀 남는데 일단 잘 되더라도 일주일만 지나도 내 코드는 아쉬움 덩어리 차후에 다시 해보기로 한다. 결과 상관없이 참여자 추첨이던 경품은 결국 하나도 못탔다.