[node.js] 백준 1920번 수 찾기

1. 문제 해석

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

1920번: 수 찾기

 

사실 이 문제를 바로 이해하는데 시간이 조금 걸렸지만 알고나면 쉬운 문제이다.

첫번째, 세번째 줄은 배열의 개수이고, 4번째 있는 줄이 2번째 있는 줄의 배열에 존재하면 1, 존재하지 않으면 0으로 나타내면 된다.

 

 

2. 문제 풀이

처음에는 for문으로 m의 배열의 값이 n의 배열에서 일치하는 값이 있는지 includes로 확인했다.

이렇게 하니까 시간초과가 나왔다.

시간을 줄이는 방법을 찾아봤다.

두가지 방법이 나왔는데,

첫번째로는 가장 많이 사용하는 이진탐색 방법이고, 두번째는 Set, has를 이용하는 방법이다.

 

for문이 왜 안되는지 시간복잡도를 먼저 따져봤다.

mArr의 각 요소가 nArr에 존재하는지 확인하기 때문에 루프가 m번 실행되고, 각 반복에서 nArr.includes() 함수가 호출된다.

includes() 함수는 배열 내에 특정 요소가 있는지를 확인하기 위해 배열을 순회하므로 O(n)의 시간이 소요된다.

따라서 시간 복잡도는 O(n * m)가 된다.

 

n과 m의 최대값은 100,000이므로 시간 복잡도는 10,000,000,000이 된다.

 

그에 반해 이진탐색의 시간 복잡도는 O(log_2 n)가 된다.

 

✔️ 이진탐색 방법이란?

정렬이 되어있는 배열의 중간의 값과  찾으려는 값을 비교하여 작으면 왼쪽으로 다시 탐색하고 크면 오른쪽으로 다시 탐색한다.

그리고 다시 범위의 중간값과 찾으려는 값을 비교해서 반으로 줄여나가 값을 찾는 방식이다.

 

✔️ Set을 사용하면 더 빠른 이유?

set의 살펴보면, 아래의 세가지 특징이 있다.

📍 동일한 값을 중복하여 포함할수 없다

📍 요소 순서에 의미가 없다

📍 인덱스로 요소에 접근할 수 없다.

 

Set은 해시테이블 자료구조를 갖고 있어서 속도가 빠르다.

삽입, 삭제 작업시 시간복잡도는 O(1)이다.

중복된 데이터가 없는 경우, 값이 있는지 확인하거나 특정 값을 삭제하는 행위가 많은 경우에 데이터를 관리하면 효율적이다.

 

✔️ Array, indexOf와 Set, has 속도 비교

Array/indexOf (0.254ms) | Set/has (0.047ms)

 

 

3. 코드

---

for문을 이용한 방법

(시간 초과)

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

const n = input[0];
const nArr = input[1].split(' ');
const m = input[2];
const mArr = input[3].split(' ');

for (let i = 0; i < n; i++) {
  if (nArr.includes(mArr[i])) {
    console.log(1);
  } else console.log(0);
}

 

---

이진탐색 방법

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

const endIdx = Number(input[0]) - 1;
const A = input[1]
  .split(' ')
  .map(Number)
  .sort((a, b) => a - b);
const B = input[3].split(' ').map(Number);

function binarySearch(arr, target, start, end) {
  while (start <= end) {
    const mid = Math.floor((start + end) / 2);

    if (target === arr[mid]) return 1;
    else if (target > arr[mid]) {
      start = mid + 1;
    } else {
      end = mid - 1;
    }
  }
  return 0;
}

const answer = B.map((b) => binarySearch(A, b, 0, endIdx));
console.log(answer.join('\n'));

첫번째 줄 값에서 -1한 값이 마지막 인덱스가 된다.

두번째 줄 값을 배열로 만들고 숫자로 변환 후 오름차순 정렬을 한다.

네번째 줄 값을 배열로 만들어서 숫자로 변환해준다.

시작값 인덱스는 0이 된다.

찾을 배열, 타겟, 시작 인덱스, 마지막 인덱스를 매개변수로 넣을 함수를 만들어 준다.

마지막 인덱스가 시작 인덱스보다 크거나 같을 경우 가운데 값은 시작 인덱스 + 마지막 인덱스에 2로 나눈값의 내림 값이다.

타켓 값과  배열의 중간값이 같을 경우 1을 반환하고,

타켓이 클 경우는 시작 인덱스를 중간값 + 1,

타겟이 작을 경우는 마지막 인덱스 - 1,

while 조건을 만족할때까지 타켓과 중간값이 같지 않으면 배열에 타겟이 없다는 의미이므로 0을 반환한다.

 

---

set, has

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

const A = input[1].split(' ').map(Number);
const B = input[3].split(' ').map(Number);

const aArr = new Set(A);
const answer = B.map((b) => (aArr.has(b) ? 1 : 0));
console.log(answer.join('\n'));

두번째줄과 네번째줄을 배열로 만든 후 숫자화해준다.

A 배열을 Set으로 선언한다.

B의 배열을 map으로 개별 요소에 접근 후 has() Set 객체에 주어진 요소가 존재하는지 여부를 판별해 반환해서

참이면(존재하면) 1, 거짓이면(존재하지 않으면) 0을 반환하도록 한다.

answer는 배열이므로 join으로 합친다.