백준 1759 < 암호 만들기 > JavaScript

📍문제 링크

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

1759번: 암호 만들기

 

📍알고리즘 분류

- 수학

- 브루트포스

- 조합론

- 백트래킹

 

📍문제 풀이

- 알파벳 N개가 주어질 때, 모음 최소 1개, 자음 최소 2개를 사용하여 만들 수 있는 암호를 모두 출력하라

- 백트래킹을 이용하여 사전순이 아니면 가지치기

 

📍의사 코드

- 백트래킹으로 가능한 경우의 수를 배열에 저장하다가, 사전 순이 어긋나면 가지치기 실행

- 사용한 알파벳을 체크할 때 isUsed 배열에 자음인지 모음인지 문자열을 저장

- 최종 depth에 도달하면, 최소 1개의 모음, 최소 2개의 자음이 있는 경우에만 답을 기

 

📍코드 (JavaScript)

const [in1, in2] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [L, C] = in1.split(" ").map(Number);
const data = in2.split(" ").sort();
const result = [];
const isUsed = [];
const answer = [];
const vowelArr = ["a", "e", "i", "o", "u"];

const recursive = (depth) => {
  if (depth === L) {
    // 모음 1개 이상 있는지 검사
    if (isUsed.filter((el) => el === "vowel").length < 1) return;
    // 자음 2개 이상 있는지 검사
    if (isUsed.filter((el) => el === "consonant").length < 2) return;
    answer.push(result.join(""));
    return;
  }

  for (let i = 1; i <= C; i++) {
    if (!isUsed[i]) {
      if (depth > 0 && result[depth - 1] > data[i - 1]) continue;
      result[depth] = data[i - 1];
      // isUsed[i] = true 대신 문자열을 저장
      isUsed[i] = vowelArr.includes(data[i - 1]) ? "vowel" : "consonant";
      recursive(depth + 1);
      isUsed[i] = false;
    }
  }
};

recursive(0);
console.log(answer.join("\n"));

 

📍리뷰

- 배열의 특정 원소의 갯수 셀 때, filter로 특정 원소만 남기고, length 프로퍼티를 사용하면 편리하다.

- 모음인지 자음인지 구별하는 방법으로, 모음을 미리 배열에 저장하고, 여기에 속하면 모음, 아니면 자음으로 구분했다.