[baekjoon] #1759 암호 만들기 (Node.js)

📖 문제

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

☃️ 풀이

백트래킹과 정규식을 활용한 방법

먼저, 입력 받은 문자열을 오름차순으로 정렬한 뒤 순회를 돌린다. pw 문자열에 차례로 문자를 추가하고 idx를 1씩 올리면서 search 함수를 재귀 호출 한다. 만약 pw 문자열의 길이가 l이고, 정규식을 만족한다면 pw를 출력한 뒤 다음 문자로 넘어간다. idx가 c 이상으로 넘어가면 바로 다음 문자로 넘어간다.

문자열의 마지막까지 순회했다면 한 칸 점프하여 다시 순회를 돌린다.

처음 작성한 정규식 /[aeiou]{1,}[^aeiou]{2,}/는 무조건 모음이 하나 이상 온 뒤 자음이 오는 경우만을 판별하여 오답 처리되었다. 그래서 자음과 모음의 가능한 배치 순서를 모두 기입하여 문제를 해결했다. 해당 문제의 경우 경우의 수가 많지 않아서 큰 문제가 없었지만, 경우의 수가 많아진다면 일일히 정규식을 작성하는 것이 어려울 수 있기 때문에 주의해야 할 필요가 있다.

💽 소스코드

const input = require('fs').readFileSync('input.txt').toString().split('\n');
const [l, c] = input.shift().split(' ').map(Number);
const string = input.shift().split(' ').sort();
const regex =
  /[aeiou]{1,}[^aeiou]{2,}|[^aeiou]{1,}[aeiou]{1,}[^aeiou]{1,}|[^aeiou]{2,}[aeiou]{1,}/;

function search(pw, idx) {
  if (pw.length === l && regex.test(pw)) return console.log(pw);
  if (idx >= c) return;

  search(pw + string[idx], idx + 1);
  search(pw, idx + 1);
}

for (let i = 0; i <= c - l; i++) {
  search(string[i], i + 1);
}