[BaekJoon] 1759 번 암호 만들기 문제 - (nodejs)

문제 번호 :  1759 번

문제 바로가기 ☞ https://www.acmicpc.net/problem/1759

---

 

<<< 문제 내용 >>>

---

 

const fs = require("fs");
const { resourceLimits } = require("worker_threads");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

let [N, M] = input[0].split(" ").map(Number);

let dicArr = input[1].split(" ");
dicArr.sort(); // 오름차순용 정렬
let visited = new Array(M).fill(false);

let tempArr = [];

const backTracking = (count, cur, arr) => {
  if (count == N) {
    let consonant = 0;
    let gather = 0;
    for (let i = 0; i < arr.length; i++) {
      if (
        arr[i] === "a" ||
        arr[i] === "e" ||
        arr[i] === "u" ||
        arr[i] === "i" ||
        arr[i] === "o"
      )
        gather++;
      else consonant++;
    }

    if (gather >= 1 && consonant >= 2) tempArr.push([...arr]);
    return;
  }

  for (let i = cur; i < dicArr.length; i++) {
    if (!visited[i]) {
      visited[i] = true;
      arr.push(dicArr[i]);
      backTracking(count + 1, i, arr);
      arr.pop();
      visited[i] = false;
    }
  }
};

backTracking(0, 0, []);

tempArr.sort();
tempArr.map((el) => console.log(el.join("")));

* 문자가 오름차순만 출력해야 된다.

처음에는 접근을 기존 문자의 모든 조합에서 오름차순인거만 찾으려고 내부 for문을 또 돌렸다가

시간초과를 맞았고, 생각해보니 처음 문자열 자체를 정렬한 후에 탐색하는 index만 탐색했던 부분 이후로만 탐색하도록

하면 되는 문제였다.

 

이 부분은 원인을 빨리 깨달았고, 고치는데 시간이 얼마 안들었지만

정규식을 이용해 자음 모음의 수를 찾아보려다가 시간을 많이썼다. 지금의 지식으로는 정규식으로 해결하지 못했다..

모음은 찾을 수 있었지만 자음을 찾기가 어려웠다ㅠㅠ..

 

좋은 정규식 방법을 아는 분은 댓글 한번 주세요.

 

 

 

 

도움이 되셨다면 공감 부탁드립니다.