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

🔗 문제 링크

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

1759번: 암호 만들기

✏️ 풀이

const [[L, C], alphabets] = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n')
  .map(row => row.split(' '));
const vowels = ['a', 'e', 'i', 'o', 'u'];
const output = [];
alphabets.sort();

const dfs = (candidate, index) => {
  if (candidate.length === +L) {
    const vowelCount = [...candidate]
    	.reduce((acc, alphabet) => acc + vowels.includes(alphabet), 0);
    const consonantCount = L - vowelCount;
    if (vowelCount >= 1 && consonantCount >= 2) {
      output.push(candidate);
    }
  } else {
    for (let i = index; i < C; i++) {
      dfs(candidate + alphabets[i], i + 1);
    }
  }
};

dfs('', 0);

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

먼저 주어진 C개의 알파벳들을 오름차순 정렬한 후, DFS를 통해 알파벳들을 앞에서부터 순서대로 L개 고른다. 이 때, 오름차순 정렬을 유지하면서 중복으로 알파벳을 선택하지 않도록 하기 위해 index 값을 저장하여 다음에 뽑을 알파벳은 이전에 뽑은 알파벳보다 index가 1 높은 알파벳들 중에서 뽑게 하였다.

 

총 L개의 알파벳을 뽑았을 때 모음의 개수와 자음의 개수를 따져서 문제의 조건인 모음 1개 이상, 자음 2개 이상을 만족할 경우 output에 push하도록 하였다. DFS가 끝난 후 output에 담긴 문자열들을 그 순서 그대로 개행 문자로 묶어서 출력하면 정답이다.