[node.js] 백준 14713번: 앵무새

🔍 14713번: 앵무새

클릭해서 문제 전체 보기🔼

📖 풀이 코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [n, ...sentences] = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");
let writing = sentences.pop().split(" ");
let sentenceArr = [];
let writingIdx = 0;

sentences.forEach((ele) => {
  let sentence = ele.split(" ");
  sentenceArr.push([sentence, 0, sentence.length]);
});

while (writingIdx < writing.length) {
  let possibility = false;

  sentenceArr.forEach((ele) => {
    if (ele[1] == ele[2]) return;

    let idx = ele[1];
    while (
      ele[0][idx] == writing[writingIdx] &&
      writing[writingIdx] != undefined
    ) {
      possibility = true;
      writingIdx++;
      idx++;
      ele[1] = idx;
    }
  });

  if (possibility === false) return console.log("Impossible");
}

for (i = 0; i < sentenceArr.length; i++) {
  let sentence = sentenceArr[i];
  if (sentence[1] != sentence[2]) return console.log("Impossible");
}

console.log("Possible");

📢 풀이 설명

문제 내용 해석
주어진 문장들 안의 단어들을 이용해, 문장의 순서의 상관없이 단어들만의 순서를 지키며 나열해서 마지막 문장을 만들수 있는지 여부를 판별하는 문제

풀이 내용은 각 문장의 idx를 늘려가며, 받아적은 문장의 단어와 비교하는 방법을 사용했다.

❗️ 이 문제에서 놓치기 쉬운 점은 "앵무새가 말한 단어를 다 받아적지 못한 경우"도 고려해야하는 것이다. ❗️

1. 앵무새가 말한 각각의 문장을 sentenceArr에 [단어들, 현재 idx, 단어 개수] 순서대로 저장했다.
2. while문을 통해 받아적은 문장을 돌며 (현재 돌고있는 단어 Idx < 받아적은 문장 속 단어의 개수) 단어 비교를 시작한다. 이때 possibility라는 불린값을 만들어둔다.
3. sentenceArr를 한바퀴 돌며, 그것의 현재 idx에 해당하는 단어와 도는 단어의 Idx에 해당하는 단어가 일치하면 둘의 idx를 1 증가시킨다.
4. 그렇게 각 문장들 속 단어 비교를 끝낸다.
5. 한 번이라도 각 문장 안에서 겹치는 단어가 있었다면 불린값을 true로 변경한다.
6. true라면 받아적은 문장이 끝날 때까지 계속 반복문을 돌고, false면 앵무새가 말하지 않은 단어를 적은 것이니 바로 "Impossible"을 출력한다.
7. 마지막으로 앵무새가 말한 단어 중 남은 것이 있는지 확인하고, 이상이 없으면 "Possible"을 출력한다.
   만약 남은 단어가 있다면 다 못 받아 적은 것이니 "Impossible"을 출력한다.

이 문제는 사용한 단어를 앞에서부터 없애는 것이기 때문에 선입선출 구조라고 볼 수 있다.
따라서 큐 알고리즘을 사용했다.