백준 10815 (nodejs)

1. 풀이1 (배열, includes)

let input = require("fs").readFileSync("/dev/stdin").toString().trim()
.split("\n")

input.shift()
input.splice(1, 1)

let arrA = input[0].split(' ').map(Number)
let arrB = input[1].split(' ').map(Number)

for(let i = 0; i <arrB.length; i++) {
    if(arrA.includes(arrB[i])) {
        arrB[i] = 1
    } else {
        arrB[i] = 0
    }
}

console.log(arrB)

처음엔 일단 하던대로 무지성 배열 + 반복문을 사용해서 풀었고, 시간 초과가 났다.

주어진 숫자들이 워낙 크고, 배열의 길이도 크기 때문에 (최대 500000)

시간 복잡도 O(n)인 include를 사용하면 제한 시간안에 답을 찾을 수가 없음.

아마 이 때쯤해서 for문, if문만 주구장창 써서 푸는 시기는 끝났다고 느낀 것 같다.

챕터 이름부터가 map, set이기도 했고, 이 두 종류의 객체에 대해 공부해야 한다고 생각했음.

 

2. 풀이2 (set, has)

그래서 set을 사용했다.

let input = require("fs").readFileSync("/dev/stdin").toString().trim()
.split("\n")

input.shift()
input.splice(1, 1)

let set = new Set (input[0].split(' '))
let arrB = input[1].split(' ')

let ans = ""

for(let i = 0; i < arrB.length; i++) {
    // set이 뭔가를 가지고 있는지 찾을 때의 시간 복잡도는 O(1)임.
    if(set.has(arrB[i])) {
        ans += "1 " 
    } else {
        ans += "0 "
    }
}

console.log(ans)

set이 어떤 요소를 가지고 있는지 없는지를 판별하는 method인 has는 시간 복잡도가 O(1)이며,

따라서 원소의 수가 많아질수록 includes를 사용할 때보다 더 시간적으로 유리하다.

이렇게 풀었더니 이건 시간 초과에 걸리지 않았음.