[JavaScript/백트래킹] 백준 골드 5 : 1759 - 암호 만들기

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

1759번: 암호 만들기

---

📌 작성한 코드

// 1759
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const [L, C] = input[0].split(" ").map(Number);
const list = input[1].split(" ").sort();

const vowels = ["a", "e", "i", "o", "u"];

const arr = new Array(L).fill("");
let answer = "";

const backTracking = (at, count, vowelCount) => {
    if (count === L) {
        if (vowelCount >= 1 && L - vowelCount >= 2) {
            answer += `${arr.join("")}\n`;
        }
        return;
    }

    for (let i = at; i < C; i++) {
        arr[count] = list[i];
        if (vowels.includes(list[i])) {
            backTracking(i + 1, count + 1, vowelCount + 1);
        } else {
            backTracking(i + 1, count + 1, vowelCount);
        }
    }
};

backTracking(0, 0, 0);
console.log(answer);

📌 설명

C개의 문자들 사이에서 사전 순으로, 중복 없이, 모음 1개, 자음 2개 이상인 L개의 문자를 선택하는 문제이다.

 

(1) 사전순 / 중복 없이 : 암호는 증가하는 형태로 존재하기 때문에 사전순으로 문자를 선택해야 한다. 

for (let i = at; i < C; i++) { // at을 사용해서 저번에 확인한 문자 다음 숫자부터
    arr[count] = list[i];
    // ...
}

(2) 모음 1개 / 자음 2개 이상 : 구한 암호가 해당 조건에 부합할 때만 답에 추가한다.

- 백트래킹을 진행할 때 모음의 개수를 매개변수로 사용해서 매 단계마다 포함하고 있는 모음의 개수를 가지고 있게 한다.

const backTracking = (at, count, vowelCount) => {
    if (count === L) {
        if (vowelCount >= 1 && L - vowelCount >= 2) { // 조건 확인
            answer += `${arr.join("")}\n`;
        }
        return;
    }

    for (let i = at; i < C; i++) {
        arr[count] = list[i];
        if (vowels.includes(list[i])) { // 모음이 있으면
            backTracking(i + 1, count + 1, vowelCount + 1); // 모음 개수 + 1
        } else {
            backTracking(i + 1, count + 1, vowelCount);
        }
    }
};

 

📌 잡담 

백트래킹 재밌다... 골드5 푸니까 재밌는거긴 하지만, bfs처럼 형식이 정해져 있어서 제약 조건만 잘 설정하면 슥슥 풀려서 풀 때 신난다.

arr.join할 때 실수로 사이에 공백을 넣어서 계속 틀렸었다. 문제를 잘못푼게 아니라 이런걸로 틀리면 정말 속상해

 

✅ 성공