[JS] 백준 1759번 : 암호만들기 - 수학,브루트포스 알고리즘,조합론,백트래킹

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

1759번: 암호 만들기

 

📋풀이방법

1. DFS에서 조합 알고리즘을 이용했다.

2. 트리는 만약 1을 뽑으면 2 3 4를 뽑고 2를 뽑으면 3 4를뽑는형태로 뻗어나간다.

3. L개를 뽑으면 L개의 알파벳을 검사한다

 -a, e, i, o ,u가 존재하면 gather라는 변수를 +1한다

 -그외에는 consonant라는 변수를 +1한다.

4.gather>=1 && consonant>=2 일 경우에만 result배열에 정답을 넣는다.

 

 

🤟내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input=input.replace(/\r/g,"").split("\n");

let [L,C]=input.shift().split(" ").map(Number);
let arr=input.shift().split(" ");

arr=arr.sort();

let result=[];
let temp=Array.from({length:L},()=>0);
function DFS(D,s){
    if(D==L){
        let gather=0;
        let consonant=0;
        for(var i=0;i<L;i++){
            if(['a','e','i','o','u'].indexOf(temp[i])!=-1){
                gather++;
            }
            else {
                consonant++;
            }
        }
        if(gather>=1&&consonant>=2) result.push(temp.slice().join(""))
        
    }
    else{
        for(var i=s;i<C;i++){
            temp[D]=arr[i];
            DFS(D+1,i+1);
            
        }
    }
}
DFS(0,0);

console.log(result.join("\n"))

 

 

💢어려웠던 점

1. DFS의 조합구하기 방식을 아직 못외웠다.

-조합구하기는 중요한 부분이므로 꼭 외워야겠다.