백준 - 숫자 카드

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다.

상근이는 숫자 카드 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을, 

아니면 0을 공백으로 구분해 출력한다.

예제 입력 1

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

예제 출력 1

1 0 0 1 1 0 0 1

제출

let fs = require('fs')
let inp = fs.readFileSync('/dev/stdin').toString().split('\n')
let have = inp[1].split(' ').map(Number)
let check = inp[3].split(' ').map(Number)
let ans = []
for(let i of check){
  if(have.includes(i)){
    ans.push(1)
  }else{
    ans.push(0)
  }
}
console.log(ans.join(' '))

처음에는 당연하게 이렇게 제출을 했었다

근데 시간초과가 나왔다

백준을 풀면서 한번도 시간초과가 나온적이 없어서 어떻게 줄여야할 지 감이 안잡혔다

문제라고한다면 includes밖에 없었다

그래서 알아보니 includes는 5를 찾는다면 인덱스를 1 2 3 4 5이렇게 모두 거쳐서 확인을 한다고 한다

그렇기 때문에 엄청 큰 숫자의 경우는 엄청난 시간이 걸리는 것이다

조금 더 찾아보니 Set객체는 그렇게 파악을 하지 않는다고 한다

Set객체는 배열이 아니라 집합의 개념이기 때문에 순서가 중요하지 않고 중복되는 요소가 없다

그래서 인덱스로 접근 하는 것이 아닌 키로 접근한다고 나와있었다

자세한 정보은 여기에 나와있다

그래서 배열이 아닌 Set으로 변경하고나니 시간 초과가 해결되었다

let fs = require('fs')
let inp = fs.readFileSync('/dev/stdin').toString().split('\n')
let have = new Set(inp[1].split(' ').map(Number))
let check = inp[3].split(' ').map(Number)
let ans = []
for(let i of check){
  if(have.has(i)){
    ans.push(1)
  }else{
    ans.push(0)
  }
}
console.log(ans.join(' '))