[Javascript] 백준 1764: 듣보잡

문제

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.

듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

출력

듣보잡의 수와 그 명단을 사전순으로 출력한다.

예제 입력 

3 4
ohhenrie
charlie
baesangwook
obama
baesangwook
ohhenrie
clinton

예제 출력 

2
baesangwook
ohhenrie

 

---

문제 풀이

중복되는 단어를 찾아 출력하면되는 단순한 문제였으나 처음 푼 방식은 시간초과가 떴습니다.

 

1. 시간초과된 코드

Input 배열을 순회하며 copy 배열에 요소를 push해주었습니다. 이때 이미 copy배열에 있는 요소라면 answer에 push 해주었습니다.

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

const copy = [];
const answer = [];

input.forEach((el) => {
  if (copy.includes(el)) {
    answer.push(el);
  } else {
    copy.push(el);
  }
});

answer.sort();

console.log(answer.length + "\n" + answer.join("\n"));

 

2. 제출된 코드

array보다 훨씬 빠른 Set을 사용해주었습니다. 듣도 못한 사람의 이름과 보도못한 사람의 이름을 각각 나누어 Nset과 Mset에 저장해주고, Nset을 순회하며 Mset이 가지고 있는 요소는 answer 배열에 push해줍니다.

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

const [N, M] = input.shift().split(" ").map(Number);
const Nset = new Set();
const Mset = new Set();
const answer = [];

input.forEach((el, idx) => {
  if (idx < N) {
    Nset.add(el);
  } else {
    Mset.add(el);
  }
});

Nset.forEach((el) => {
  if (Mset.has(el)) answer.push(el);
});

answer.sort();
console.log(answer.length + "\n" + answer.join("\n"));