암호 만들기

문제

언어

  • JavaScript

문제 풀이 step 1

  • 백준 15650번 - N과 M (2) 풀이 에서 풀었던 방식을 이용해서 풀 수 있습니다.
  • 문제에서 “암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것” 이라고 했으니, 입력 받은 문자들을 사전 순으로 정렬합니다.
  • 그리고 문자들을 하나씩 선택하는 경우와 선택하지 않는 경우 이렇게 2 가지로 나눠서 재귀 호출을 합니다.
  • 재귀 호출의 구조에 따라서 나눠보겠습니다.
    1. 불가능 한 경우
      • 최소 한 개의 모음과 두 개의 자음으로 구성되지 않은 경우
    2. 정답을 찾는 경우
      • 선택하는 경우들로 이루어진 문자의 갯수가 l 개가 된 경우
    3. 다음 경우 호출
      • 선택한 문자의 갯수가 l 개보다 적은 상황에서 다음 문자를 선택하는 경우와 선택하지 않는 경우

소스 코드 1

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

// 모음이 1개 이상인지 그리고 자음이 2개 이상인지 비교하는 함수
const check = (password) => {
	const collection = password.filter(
		(v) => v === "a" || v === "e" || v === "i" || v === "o" || v === "u"
	).length;
	const consonant = password.length - collection;

	return collection >= 1 && consonant >= 2;
};

const rec = (l, c, arr, res, password, index, depth) => {
	if (depth === l) {
		if (!check(password)) return;

		res.push(password.join(""));
		return;
	}

	// index 가 주어진 문자들의 개수를 넘어가는 경우
	if (index >= c) return;

	// 문자 선택함
	password.push(arr[index]);
	rec(l, c, arr, res, password, index + 1, depth + 1);

	// 문자 선택하지 않음
	password.pop();
	rec(l, c, arr, res, password, index + 1, depth);
};

const solution = (input) => {
	const [l, c] = input[0].split(" ").map(Number);
	const arr = input[1].split(" ").sort();

	const res = [];
	const password = [];
	rec(l, c, arr, res, password, 0, 0);

	return res.join("\n");
};

console.log(solution(input));