[백준/node.js] 10815 숫자카드

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

10815번: 숫자 카드

• 사용언어 : node.js
• 알고리즘 : 자료구조, 정렬, 이분 탐색
• Solved.ac Tier : Silver V

node.js 코드

1. 문제 정리

총 4줄의 입력이 들어온다. 첫번째 줄 입력은 상근이가 가지고 있는 숫자 카드의 개수 N, 그 다음은 상근이가 가지고 있는 N개의 숫자 카드들, 그리고 정수 M, 그리고 M개의 숫자 카드들이 주어진다. M개의 정수 카드와 상근이가 가진 카드를 비교 해보는 간단한 문제였다. 

 

2. 문제 접근

처음엔 문제 접근을 간단하게 includes 함수로 해보았다. 

const filePath = process.platform === 'linux' ? '/dev/stdin' : 'ans.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split("\n");
let N = input[0], N_cards = input[1].split(" "), M = input[2], M_cards = input[3].split(" ");
M_cards.map((value)=>{
    let find = N_cards.includes(value);
    process.stdout.write(find ? "1 ":"0 ")
})

당연하게도 시간 초과가 발생 하였고, 애초에 하나하나 출력 하는 것이 말이 안되는 문제였다. 총 50만개의 카드를 비교 해야 할 수도 있기 때문이다. 따라서 무작정 하나하나 map으로 비교하는 문제가 아니였다. 이분 탐색을 사용 할 수도 있으나, 더 빠른 SET으로 문제를 해결 하였다. 

3. 완성 코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : 'ans.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split("\n");
let N = input[0], N_cards = new Set(input[1].split(" ")), M = input[2], M_cards = input[3].split(" ");

const result = [];
for(let card of M_cards){
    N_cards.has(card) ? result.push(1):result.push(0);
}

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