[백준(BOJ)] 1759- 암호 만들기

 

1759번: 암호 만들기

---

문제

암호 만들기 문제

제한 사항

 (3 ≤ L ≤ C ≤ 15)

문제 풀이

이 문제는 dfs를 활용해서 백트래킹을 할 수 있는지 없는지 물어보는 문제인 것 같다(조합).

 

문제를 풀 때 자음과 모음 개수에 대해서 제약이 있는데, 모음은 최소 1개 이상, 그리고 자음은 최소 2개 이상으로 구성되어 있다는 것이다.

 

이 때문에 본인은 다음과 같이 dfs 함수의 매개변수로 모음의 개수를 넘겨주어 이를 계산할 수 있도록 하였다.

const dfs = (cnt, st, key, aeiouCnt) => {
	// code
    
    // 만약 모음이 없거나, 모음의 개수가 너무 많아 자음이 2개 이상 오지 못하는 경우를 체크
    if (aeiouCnt < 1 || aeiouCnt > L - 2) return;
    
  	// code
};

그런 다음 주어진 문자 배열을 먼저 정렬해준 뒤, 백트래킹을 돌며 dfs의 끝에서(cnt와 L이 같을 때) 위와 같이 모음의 개수를 체크해주어 해당 문자열을 최종적인 정답 배열에 push 해준다.

 

그리고 해당 정답 배열을 정렬해주게 되면 문제에서 요구한 정답들을 구한 것이 된다.

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const [L, C] = input
  .shift()
  .split(' ')
  .map(x => +x);
const characters = input[0].split(' ').sort();
const aeiou = new Set(['a', 'e', 'i', 'o', 'u']);
const ans = [];

const dfs = (cnt, st, key, aeiouCnt) => {
  if (cnt === L) {
    if (aeiouCnt < 1 || aeiouCnt > L - 2) return;
    ans.push(key);
    return;
  }

  for (let i = st; i < characters.length; i++) {
    const c = characters[i];
    dfs(cnt + 1, i + 1, key + [c], aeiouCnt + (aeiou.has(c) ? 1 : 0));
  }
};

dfs(0, 0, [], 0);
console.log(ans.sort().join('\n'));