[백준 - Node.js] 암호 만들기 1759번

문제 설명

https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

---

문제 풀이

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];
let count = 0;
let n = 0;

rl.on('line', function (line) {
  if (!count) {
    let arr = line.split(' ');
    n = +arr[0];
  } else {
  // 미리 정렬
    input = line.split(' ').sort();
  }
  count++;
}).on('close', function () {
  solution(input);
  process.exit();
});

// 필터함수 => 모음 기준으로 최소 1개 그래고 자음의 자리 최소 2개 남겨줌
const filter = arr => {
  const vowel = ['a', 'e', 'i', 'o', 'u'];
  let ctn = 0;
  for (let alpha of arr) {
    if (vowel.includes(alpha)) ctn++;
  }
  if (ctn >= 1 && ctn <= n - 2) return true;
  return false;
};

const solution = input => {
  // 초기세팅
  const visited = new Array(input.length - 1).fill(false);
  const arr = [];
  let answer = [];

  // dfs
  const dfs = (count, idx) => {
    // base case => 자릿수와 필터함수 기준
    if (count === n && filter(arr)) {
      answer.push(arr.join(''));
      return;
    }
    // input순회
    for (let i = idx; i < input.length; i++) {
      // 방문X 백트래킹
      if (!visited[i]) {
        arr.push(input[i]);
        visited[i] = true;
        dfs(count + 1, i);
        arr.pop();
        visited[i] = false;
      }
    }
  };
  dfs(0, 0);
  // 다시정렬
  console.log(answer.sort().join('\n'));
};