[boj] 1062. 가르침 (node.js)

문제 요약

[boj] 1062. 가르침 (node.js)

풀이

너무 어렵게 푼 것 같은 감이 있다.. ㅠㅠ 크게 입력받고 전처리하는 부분, 재귀 함수, 점수 계산 함수의 세 파트로 나눌 수 있다.

const solution = () => {
  let arr = [];
  let cand = [];
  const [N, letters] = input().split(" ").map(Number);
  if (letters < 5) {
    console.log(0);
    process.exit();
  }

  for (let i = 0; i < N; i++) {
    let temp = input();
    if (temp.length == 8) continue;
    temp
      .slice(4, temp.length - 4)
      .split("")
      .forEach((char) => {
        if ("acint".includes(char)) return;
        if (!arr[i]) arr[i] = "";
        arr[i] += char;
        if (cand.includes(char)) return;
        cand.push(char);
      });
  }
  if (cand.length <= letters - 5) {
    console.log(N);
    process.exit();
  }
  let result = 0;
  let used = [];
  arr = arr.filter((elem) => elem);
  rec(0);
  if (arr.length < N) result += N - arr.length;
  console.log(result);

  function rec(k) {
    if (k == letters - 5) {
      result = Math.max(evaluate(), result);
      return;
    }
    for (let i = 0; i < cand.length; i++) {
      let char = cand[i];
      if (used[char.charCodeAt(0)]) return;
      used[char.charCodeAt(0)] = 1;
      rec(k + 1);
      used[char.charCodeAt(0)] = 0;
    }
  }

  function evaluate() {
    let score = 0;
    for (let i = 0; i < arr.length; i++) {
      let words = arr[i].split("");
      let add = true;
      for (let j = 0; j < words.length; j++) {
        if (!used[words[j].charCodeAt(0)]) {
          add = false;
          break;
        }
      }
      if (add) score++;
    }
    return score;
  }
};

anta ~ tica -> 5개의 문자 'acint' 는 모든 단어에 포함되므로 항상 배워야 한다.
따라서 입력받은 문자열에서 anta-tica를 제외하고 슬라이싱한다.
각 단어별로 배워야 하는 문자들을 문자열 형태로 arr에 저장한다.
배워야 하는 문자들은 중복되지 않도록 cand에 저장한다.

이렇게 세팅한 후, cand 에서 재귀함수를 구현해 문자를 고르고 고른 문자들을 선택했을 때의 점수를 계산해 최대치를 매번 갱신한다. 재귀함수의 종료 조건은 (k-5)개가 선택되는 경우 종료한다. (문자들 중 acint는 무조건 선택해야 하기 때문)

이 로직으로 구현하면, 재귀함수 이전에 테스트케이스를 입력받으며 사전 처리해줄 수 있는 경우가 여러 개 있다. 단어를 '배운다'의 기준은 단어를 구성하는 모든 문자열을 아는 것이다. 따라서 k(코드에서는 letters로 표현)를 입력받자마자 (k < 5)이면 acint 조차 만족시키지 못하므로 어떤 단어도 배울 수 없어 바로 0을 출력한다. 또, 단어의 길이가 8인 경우는 'antatica'이므로 continue 해준다.

이 로직에서 문제를 풀이할 때 cand배열은 중복되지 않는 단어들을 저장했고, arr 배열은 중복 여부와 무관하게 해당 배열에서 acint가 아닌 문자를 저장한다. 입력을 모두 받은 후 arr.filter로 비어 있는 값(acint를 포함하므로 자동으로 완성되는 값)은 모두 삭제하는 로직이 들어가므로, 점수를 계산한 이후에 이를 다시 더해주었다.

rec 함수는 일반적인 재귀 함수, evaluate 함수는 used 배열을 이용해 arr[i]에 저장해둔 문자열이 used된 문자열의 구성으로 만들어질 수 있으면 점수를 더하는 로직을 구현했다.

생각

• 코드 작성 40분, 디버깅 40분 정도 걸려서 장장 한 시간 반 정도 풀었다.
• 코드 한 줄 한 줄의 수행 순서에 따라 로직이 달라진다! 순서에 유의하자.

전체 풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const solution = () => {
  let arr = [];
  let cand = [];
  const [N, letters] = input().split(" ").map(Number);
  if (letters < 5) {
    console.log(0);
    process.exit();
  }

  for (let i = 0; i < N; i++) {
    let temp = input();
    if (temp.length == 8) continue;
    temp
      .slice(4, temp.length - 4)
      .split("")
      .forEach((char) => {
        if ("acint".includes(char)) return;
        if (!arr[i]) arr[i] = "";
        arr[i] += char;
        if (cand.includes(char)) return;
        cand.push(char);
      });
  }
  if (cand.length <= letters - 5) {
    console.log(N);
    process.exit();
  }
  let result = 0;
  let used = [];
  arr = arr.filter((elem) => elem);
  rec(0);
  if (arr.length < N) result += N - arr.length;
  console.log(result);

  function rec(k) {
    if (k == letters - 5) {
      result = Math.max(evaluate(), result);
      return;
    }
    for (let i = 0; i < cand.length; i++) {
      let char = cand[i];
      if (used[char.charCodeAt(0)]) return;
      used[char.charCodeAt(0)] = 1;
      rec(k + 1);
      used[char.charCodeAt(0)] = 0;
    }
  }

  function evaluate() {
    let score = 0;
    for (let i = 0; i < arr.length; i++) {
      let words = arr[i].split("");
      let add = true;
      for (let j = 0; j < words.length; j++) {
        if (!used[words[j].charCodeAt(0)]) {
          add = false;
          break;
        }
      }
      if (add) score++;
    }
    return score;
  }
};

let line = 0;
const input = () => stdin[line++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  solution();
  process.exit();
});