[백준][문자열] 전화번호 목록 NodeJs 구현

목차

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

문제

 

문제 구현 방향

여러 방식으로 풀 수 있다 트라이 알고리즘, 정렬 해쉬맵이 있는데 정렬하고 트라이 알고리즘으로 푼 방식만 소개하고자 한다.

 

코드 구현

트라이 알고리즘 방식

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

let t = Number(input[0]);
input.splice(0, 1);

class Trie {
  constructor() {
    this.finish = false;
    this.nodes = new Array(10).fill(null);
  }

  insert(str) {
    if (str.length === 0) {
      this.finish = true;
      return;
    }
    const cur = parseInt(str[0]);
    if (this.nodes[cur] === null) {
      this.nodes[cur] = new Trie();
    }
    this.nodes[cur].insert(str.slice(1));
  }

  find(str) {
    if (str.length === 0) {
      return false;
    }
    if (this.finish) {
      return true;
    }

    const cur = parseInt(str[0]);
    if (this.nodes[cur] === null) {
      return false;
    }
    return this.nodes[cur].find(str.slice(1));
  }
}

for (let i = 0; i < input.length; i++) {
  let dic = [];
  const root = new Trie();
  let n = Number(input[i]);
  for (let j = i + 1; j <= i + n; j++) {
    dic.push(input[j].trim());
    root.insert(input[j].trim());
  }
     let flag = false;

    for (let k = 0; k < dic.length; k++) {

   
      if (root.find(dic[k])) {
        flag = 1;
        break;
      }
    }
    if (flag) console.log("NO");
    else console.log("YES");

  i += n;
}

 

정렬 방식

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin")
	.toString()
	.split("\n");

let idx = 0;
let number = +input[idx++];

while (number--) {
	let num = +input[idx++];
	let arr = [...Array(num)].map(() => input[idx++]).sort();
	let len = 0;
	let result = "YES";

	for (let i = 1; i < num; i++) {
    
		if (arr[i].slice(0, arr[i-1].length) === arr[i - 1]) {
			result = "NO";
			break;
		}

	}
	console.log(result);
}