백준_10815: 숫자 카드 (node.js/JavaScript)

➡️ 문제: 숫자 카드

 

🍈 제출

let input = require('fs').readFileSync(0).toString().trim().split('\n');
let [n, m] = [new Set(input[1].split(' ').map(Number)),(input[3].split(' ').map(Number))];
let x = [];
for (let i = 0; i < m.length; i++) {
    x.push(n.has(m[i]) ? 1 : 0);
}
console.log(x.join(" "));

 

 

🥒 과정

 

다음은 처음에 제출했던 코드다. (시간 초과)

let input = require('fs').readFileSync(0).toString().trim().split('\n');
let n = input[1].split(' ').map(Number);
let m = input[3].split(' ').map(Number);
let x = [];
m.forEach((e) => x.push(n.includes(e) ? 1 : 0));
console.log(x.join(' '));

 

이 코드에서 브루트포스 탐색기법(모든 요소에 대해 n 배열을 검색하므로 전체 시간 복잡도는 O(m * n)이 됨)

)을 사용했기 때문에 시간초과가 났다.

 

문제에서 두 숫자 카드에 같은 수가 적혀있는 경우는 없다고 했으니 상근이가 가지고 있는 카드 배열(위 코드에서는 n)을 Set으로 변환해서 탐색하기로 했다. 

 

Set의 has 메서드는 평균적으로 O(1)의 시간 복잡도를 가진다. 제출한 코드로 실행하면 전체 시간 복잡도는 O(m)가 되게 된다!