[백준] 10816 숫자 카드 2 Node.js

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

예제 입력 1

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

예제 출력 1

3 0 0 1 2 0 0 2

---

문제풀이

💡 문제풀이 과정

• N의 최대값 500,000 그리고 M의 최대값도 500,000이다. N과 M의 값을 순차적으로 비교 시 최악의 경우 500,000 * 500,000 = 250,000,000,000번 (2500억번)
• 시간 제한은 1초이고 최대 1억번까지의 연산이 가능하므로 이진 탐색 또는 해당 문제의 경우 key-value 형태의 Object를 이용하여 개수를 카운트하기 위해 Map() 함수한 방법과 Object()를 이용한 풀이를 비교해 봤다.
• 아무래도 Object보다는 시간과 메모리 사용 측면에서 ES6문법의 Map() 함수가 더 좋은 결과였다.

✅ 답안 #1: Map(), for … of를 이용한 풀이

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const Ncards = input[1].split(' '); // 상근이가 갖고 있는 카드 리스트
const Mcards = input[3].split(' '); // 확인해야 하는 카드 리스트
const result = []; 
const map = new Map(); // 카드 소유 여부와 개수를 저장하기 위한 Map 생성

// 상근이가 가지고 있는 카드 숫자와 카드 개수를 map에 저장하기 위한 반복문
for (card of Ncards) {
  // map에 상근이의 카드 숫자와 동일한 값이 있다면, 해당 value에 1 더하기 
  if (map.has(card)) map.set(card, map.get(card) + 1);
  // 동일한 값 없다면, 해당 vaule 1로 저장
  else map.set(card, 1);
}

// 확인해야 하는 카드 리스트를 탐색하기 위한 반복문
for (card of Mcards) {
  // map에 해당 카드있으면 카드 숫자(key)의 개수(value)를 담고, 없으면 0 담기  
  result.push(map.get(card) || 0);
}

console.log(result.join(' '));

✅ 답안 #2: Object(), forEach()를 이용한 풀이

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const Ncards = input[1].split(' ').map(Number);
const Mcards = input[3].split(' ').map(Number);
const obj = new Object();
const result = [];

Ncards.forEach((v) => {
  obj[v] ? obj[v]++ : (obj[v] = 1);
});

Mcards.forEach((v) => {
  result.push(obj[v] || 0);
});

console.log(result.join(' '));