초기코드

/*
 * 서로 다른 L개의 알파벳 소문자
 * 최소 한 개의 모음
 * 최소 두 개의 자음
 * 알파벳이 증가하는 순서로 배열
 * 암호로 사용했을 법한 문자의 종류 C개
 */

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
  .toString()
  .trim()
  .split("\n");

const [L, C] = input[0].split(" ").map(Number);

const chars = input[1].split(" ").sort();

const isVowel = (char) =>
  ["a", "e", "i", "o", "u"].includes(char.toLowerCase());

const vowelFounds = Array(C).fill(false); // 모음인 경우 true의 값을 갖는 배열

for (let i = 0; i < C; i++) {
  if (isVowel(chars[i])) {
    vowelFounds[i] = true;
  }
}

// result에 모음(true)이 1개 이상, 자음(false)이 2개 이상

console.log(chars);
console.log(vowelFounds);

const result = [];

function findPassword(vowelFounds) {
  let vowelcnt = 0; // 모음의 갯수
  let notVowelcnt = 0; // 자음의 갯수
  let depth = 0;
  let temp = [];

  for (let i = 0; i < C; i++) {
    temp.push(chars[i]);

    if (vowelFounds[i]) {
      vowelcnt++;
    } else {
      notVowelcnt++;
    }

    depth++;
  }

  if (depth === L) {
    if (vowelcnt >= 1 && notVowelcnt >= 2) {
      result.push(temp);
    }
  }
}

findPassword(vowelFounds);

console.log(result);

재귀(Recursion) 구조가 아니라서 모든 조합을 탐색할 수 없음

→ 어떻게 모든 조합을 탐색해야할까

백트랙킹 기법 사용

"문자를 선택했을 때"와 "선택하지 않았을 때"를 모두 따져봐야함

백트랙킹 적용

const result = [];
const temp = [];

// index: 탐색 위치, depth: 현재 뽑은 개수
// vCnt: 현재까지 뽑은 모음 개수, nVCnt: 현재까지 뽑은 자음 개수
function findPassword(index, depth, vCnt, nVCnt) {
  if (depth === L) {
    if (vCnt >= 1 && nVCnt >= 2) {
      result.push(temp.join(""));
    }
    return;
  }

  for (let i = index; i < C; i++) {
    temp.push(chars[i]);

    // 선택한 문자가 모음인지 자음에 따라 카운트를 늘려서 재귀 호출
    // 내부에서 재귀로 탐색위치를 증가시키면서 chars 탐색
    if (vowelFounds[i]) {
      findPassword(i + 1, depth + 1, vCnt + 1, nVCnt);
    } else {
      findPassword(i + 1, depth + 1, vCnt, nVCnt + 1);
    }

    // 앞에 if문이 있어서 depth === L 조건만족 시, return되므로 함수 호출했던 for문의 위치로 돌아감
    temp.pop();
  }
}

findPassword(0, 0, 0, 0);
console.log(result);

L=3이고 a, b, c, d를 탐색할 때:

1. temp에 [a, b, c]를 넣고 depth === 3이 되어 result에 저장 후 return.
2. 직전으로 돌아와서 c를 pop(). (temp는 다시 [a, b])
3. for문이 다음으로 넘어가서 d를 push(). (temp는 [a, b, d])
4. 다시 depth === 3이 되어 result에 저장 후 return.