[Baekjoon] 1764번 듣보잡 - Javascript

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

1764번: 듣보잡

문제

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

입력

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

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

출력

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

예제 입력 1 복사

3 4
ohhenrie
charlie
baesangwook
obama
baesangwook
ohhenrie
clinton

예제 출력 1 복사

2
baesangwook
ohhenrie

 

문제풀이(1)

N = 듣도 못한 사람의 수, M = 보도 못한 사람의 수
듣도 못한 사람과 보도 못한 사람들의 이름에는 중복이 없다.
이진탐색을 사용해서 탐색한다.

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";

const input = require("fs").readFileSync(filePath).toString().trim().split("\n");
const [N, M] = input.shift().split(" ").map(Number);

const peopleN = input.slice(0, N).sort();
const peopleM = input.slice(N).sort();

let answer = [];

const binarySearch = (arr, target) => {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);

    // 중간값이 타겟과 일치하는 경우
    if (arr[mid] === target) {
      return target;
    }

    // 중간값이 타겟보다 작으면 오른쪽 부분 탐색
    if (arr[mid] < target) {
      low = mid + 1;
    } else if (arr[mid] > target) {
      // 중간값이 타겟보다 크면 왼쪽 부분 탐색
      high = mid - 1;
    } else {
      return target;
    }
  }

  return false;
};

const [longArr, shortArr] = N > M ? [peopleN, peopleM] : [peopleM, peopleN];

shortArr.forEach((name) => {
  let peopleNM = binarySearch(longArr, name);
  if (peopleNM) {
    answer.push(peopleNM);
  }
});

console.log(`${answer.length}\n${answer.join("\n")}`);

 

문제풀이(2)

이진탐색을 사용하지 않은 풀이
이진탐색을 했을경우보다 메모리는 많이 사용하지만 실행시간은 줄었다.
문제풀이(1)-이진탐색o : 메모리 23056kb, 실행시간 364ms
문제풀이(2)-이진탐색x : 메모리 30660kb, 실행시간 256ms

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";

const input = require("fs").readFileSync(filePath).toString().trim().split("\n");
const [N, M] = input.shift().split(" ").map(Number);

const map = new Map();
const answer = [];

for (let i = 0; i < input.length; i++) {
  if (map.has(input[i])) {
    answer.push(input[i]);
  } else {
    map.set(input[i]);
  }
}

console.log(`${answer.length}\n${answer.sort().join("\n")}`);