[백준 1920번] 수 찾기 - JavaScript

 

이 문제는 첫번째 숫자들의 모음에 두번째 숫자들이 포함되어있는지를 출력해야하는 문제이다.

 

우선 이 문제도 먼저 무식하게 풀어보겠다.

 

 

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

const numA = +input.shift();
const numsA = input.shift().split(' ').map(Number);
const numB = +input.shift();
const numsB = input.shift().split(' ').map(Number);

const compared = Array(numA).fill(0);

for (let i = 0; i < numA; i++) {
	for (let j = 0; j < numB; j++) {
		if (numsA[i] === numsB[j]) {
			compared[i] = 1;
		}
	}
}

compared.forEach((item) => console.log(item));

 

 

시간 초과...........

 

그리고 나서 문제를 다시 읽어보니 N(1 ≤ N ≤ 100,000), M(1 ≤ M ≤ 100,000) 의 범위이다.

만약 이중 for문을 사용하여 코드를 작성한다면, N x M만큼 반복이 진행되므로 시간이 오래걸릴 수밖에 없다.

 

따라서 우리는 for문 말고 다른 방법을 사용해야한다.

 

Set을 사용하면 해당 데이터가 있는지 여부를 O(1)의 시간 복잡도로 알 수 있다.

또한 Set은 중복을 제거하기 때문에, 처음에 오는 데이터만 Set으로 관리해야한다.

 

 

소스 코드

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

const numA = +input.shift();
const numsA = new Set(input.shift().split(' ').map(Number));
const numB = +input.shift();
const numsB = input.shift().split(' ').map(Number);

const result = numsB.map((num) => (numsA.has(num) ? 1 : 0));
console.log(result.join('\n'));

 

Javascript의 .has()를 사용하여 보다 간결하게 코드를 작성하였다.