서문

이 문제는 프로그래머스에서 "완전탐색"으로 분류가 되어있는 문제다. 그래서 그냥 모든 경우에 대해 검사를 해주면 된다.

보통 사람들은 어떤 문제를 풀 때, 완전탐색이라고 알고 풀면 대게 잘 풀기 마련이다. 하지만 해당 문제가 어떤 알고리즘으로 접근해야 하는지 모르는 경우에서는 완전탐색인지 바로 알기가 쉽지않다.

그래서 계속해서 많은 연습이 필요한 알고리즘 같다. 하나의 문제를 봤을 때, 해당 문제가 어떤 알고리즘으로 접근해야 가장 좋을지 판단하는 것도 실력이기 때문이다. 많이 풀다보면 자연스레 보이기 시작할 것 같다.

소스 코드

// 가능한 모든 조합을 뽑은 후
// 합쳐진 숫자가 유효한지 검사
// 그 후, 소수인지 검사
// 소수이면 배열에 추가
// 배열의 길이를 반환

function solution(numbers) {
  let answer = [];
  const cards = numbers.split('');

  for (let i = 1; i <= numbers.length; i++) {
    const data = perm(cards, i);

    for (const strNum of data) {
      if (strNum[0] === '0') continue;
      const num = Number(strNum);
      let count = 0;

      for (let i = 1; i <= num; i++) {
        if (num % i === 0) {
          count++;

          if (count > 2) break;
        }
      }

      if (count === 2 && !answer.find(item => item === num)) {
        answer.push(num);
      }
    }
  }

  return answer.length;
}

function comb(arr, selectNumber) {
  const results = [];
  if (selectNumber === 1) return arr.map(value => value);

  arr.forEach((fixed, index, origin) => {
    const rest = origin.slice(index + 1);
    const combinations = comb(rest, selectNumber - 1);
    const attached = combinations.map(combination => fixed + combination);

    results.push(...attached);
  });

  return results;
}

function perm(arr, selectNumber) {
  const results = [];
  if (selectNumber === 1) return arr.map(value => value);

  arr.forEach((fixed, index, origin) => {
    const rest = [...origin.slice(0, index), ...origin.slice(index + 1)];
    const permutations = perm(rest, selectNumber - 1);
    const attached = permutations.map(permutation => fixed + permutation);

    results.push(...attached);
  });

  return results;
}

문제 풀이

나는 이 문제를 순열을 써서 모든 가능한 경우에 대해 검사를 해 주었다. 자바로 알고리즘을 한창 할 때에는 순열과 조합 알고리즘 사용법을 기억했었는데 오랜만에 하니까 또 잊어버리고 말았다. 그래서 이젠 자바스크립트로 순열과 조합을 구현하는 방법을 배울 겸 둘 다 구현해보았다.

조합 - Combination

조합은 n개의 집합에서 순서상관없이 r개의 데이터를 선택하는 것이다. 이를 알고리즘으로 구현할 때는 재귀적으로 구현한다.

매개변수 arr

이 매개변수로 받는 배열 arr는 전체 데이터가 속한 집합을 의미한다.

매개변수 selectNumber

이 매개변수는 해당 arr에서 몇 개의 데이터를 선택할 건지에 대한 변수이다. 즉 arr에서 selectNumber의 개수만큼 뽑는다는 뜻이다.

조합 알고리즘은 위에서 말한 것 처럼 순서는 상관이 없기때문에, 구현할 때

const rest = origin.slice(index + 1);

처럼 해주면 된다. 여기서 rest는 뽑은것을 제외한 나머지 데이터들을 의미한다. 또 fixed는 지금까지 뽑은 데이터들을 의미한다. 그래서 하나 뽑았으므로 다시 재귀적으로 호출해준다.

comb(rest, selectNumber - 1); 

selectNumber에서 1을 빼주는 이유는 하나를 선택했기 때문에 그 만큼 빼주는 것이다.

이렇게 진행하다가 selectNumber가 1이 되는 순간,

return arr.map(value => value);

을 반환해준다. 이 코드의 의미는 남은 데이터들 중 각각 하나씩 뽑을 수 있으므로 모든 경우에 대해 하나씩 뽑아 반환해준다는 의미이다.

위의 설명처럼 진행하면 attached변수에 모든 가능한 조합의 경우가 반환된다. 그 후 원하는 나머지 조건을 토대로 검사해주면서 답을 찾으면 된다.

순열 - Permutation

조합과 거의 비슷하게 구현이 된다. 차이가 있다면, 순열은 조합과 달리 순서가 중요하다. 따라서 rest를 만들 때 아래와 같이 만들어준다.

const rest = [...origin.slice(0, index), ...origin.slice(index + 1)];

위 코드를 보면 해당 뽑은 index를 제외한 나머지 데이터들에 대해 고려해준 것이다. index를 기준으로 전 데이터와 후 데이터를 뽑아 rest를 구성해주는 모습이다.

그 다음 이를 토대로 조합 알고리즘과 마찬가지로 아래와 같이 재귀적으로 호출해준다.

const permutations = perm(rest, selectNumber - 1);

조합과 똑같이 호출해줄 때는 selectNumber를 1 감소시켜 호출한다. 그래야 종료조건에 걸려 무한 호출을 막아줄 수 있다.

그럼 또 attached 변수에 모든 경우에 대한 순열의 결과가 반환된다. 이를 각각 result에 넣어준다음 반환해준다.

해당 문제는 순열을 사용해서 해결했다. 순서에 따라 완전히 다른 수가 되기 때문이다. 그래서 위에서 구현한 순열 알고리즘을 사용해 모든 경우에 대해 데이터를 구성하고, 각각의 데이터가 소수인지 아닌지를 검사해주었다. 그래서 만약 소수이면 answer에 그 소수를 넣어주고 최종적으로 answer의 길이를 반환해주면 정답이 된다.

후기

하루하루 알고리즘 문제를 풀 때마다, 내가 아직 많이 부족하다는 생각이 든다. 예전에 다 했었던 알고리즘들인데 기억이 안날 때마다 반성하게 된다. 미리미리 알고리즘을 꾸준하게 했으면 지금쯤 더욱 실력이 좋았을텐데 하고 후회도 한다. 하지만 더 이상 후회를 하고싶지 않기 때문에 이제부터라도 꾸준히 알고리즘을 풀 것이다.

이 문제도 간만에 순열과 조합에 대해 정리할 수 있어서 좋았다. 앞으로 블로그에 알고리즘 설명 시리즈를 만들건데, 이에 대해서도 자세하게 정리해야겠다.