[백준] 1759 암호 만들기- javascript

📌 문제

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

📌 풀이

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

const [L, C] = input.shift().split(' ').map(Number);
const alphabet = input.shift().split(' ').sort();
const vowel = ['a', 'e', 'i', 'o', 'u'];
const answer = [];

function backtracking(str, startIndex) {
  if (str.length === L) {
    let cnt = 0;
    for (let i = 0; i < str.length; i++) {
      if (vowel.includes(str[i])) cnt++;
    }
    if (cnt > 0 && L - cnt > 1) {
      answer.push(str);
    }
    return;
  } else {
    for (let i = startIndex; i < C; i++) {
      backtracking(str + alphabet[i], i + 1);
    }
  }
}

backtracking('', 0);

console.log(answer.join('\n'));

✔ 알고리즘 : 백트래킹 + 브루트포스

✔ 조합 문제로 조건으로는 모음이 1개 이상, 자음이 2개 이상인 문자열을 조합하는 문제

✔ 백트래킹을 통해 문자열을 만들어 나간다. 길이가 L이 되었을 때 조건판단을 통해 조건에 부합하면 answer에 넣어준다

✔ 입력조건에서 L,C 범위가 크지 않기 때문에 모든 경우를 탐색해도 시간초과가 발생하지 않는다

✔ 난이도 : 백준 기준 골드 5