[백준1759_자바스크립트(javascript)] - 암호 만들기

🔴 문제

암호 만들기

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [lc, inputs] = fs.readFileSync(path).toString().trim().split('\n');
const [l, c] = lc.split(' ');
const vowels = ['a', 'e', 'i', 'o', 'u'];
const letters = inputs.split(' ').sort();
const passwords = [];

const isVowel = (letter) => {
  return vowels.includes(letter);
};

const backTracking = (pw, n, vCnt, cCnt) => {
  if (n >= Number(l)) {
    if (vCnt >= 1 && cCnt >= 2) passwords.push(pw.join(''));
    return;
  }
  for (const letter of letters) {
    if (pw[n - 1] >= letter) continue;
    if (vowels.includes(pw)) continue;

    if (isVowel(letter)) {
      backTracking([...pw, letter], n + 1, vCnt + 1, cCnt);
    } else {
      backTracking([...pw, letter], n + 1, vCnt, cCnt + 1);
    }
  }
};

for (const letter of letters) {
  if (isVowel(letter)) {
    backTracking([letter], 1, 1, 0);
  } else {
    backTracking([letter], 1, 0, 1);
  }
}

for (const password of passwords) {
  console.log(password);
}

🟢 풀이

⏰ 소요한 시간 : 45분(근데 겜하면서 함)

먼저 L개의 단어를 중복없이 선택한다는점에서 백트래킹으로 풀어야겠다는 생각을 했다.
또한 연산 횟수를 줄여주기 위해서 암호가 될수있는 문자 letters를 정렬해줬다.문제정렬에서 조금 헤맴ㅠ..

그 후 for문을 순회하면서 정렬된 letters배열의 letter들을 하나씩 돌며 백트래킹을 수행해줬다.

백트래킹 함수는 처음엔 내가 선택한 암호 배열pw, 두 번째는 내가 몇 개를 선택했는지 알아볼 수 있는 n, 마지탁 탈출조건에서 확인할 모음, 자음개수를 의미하는 vCnt, cCnt 총 4개의 파라미터를 전달 받는다.

내부 구현은 백트래킹 알고리즘에 맞게 l 개의 단어를 다 선택했을 경우 그 암호가 올바른 암호인지(자음개수와 모음개수를 만족하는지) 확인한 후 정답인 password배열에 넣어준다

만약 l 개의 단어를 다 선택하지 못했을 경우 백트래킹을 수행해주면 되는데 이때 오름차순을 만족하는지, 중복은 없는지 확인을 해준뒤에 수행해준다.
그리고 다시 선택한 문자가 자음인지 모음인지에 따라 파라미터로 전달되는 값을 업데이트 해준다.

🌟 기억할점

• 문자열 정렬은 sort() 기본으로 (ex : Array.sort())

🔵 Ref