[백준 알고리즘] 1920번: 수 찾기 (JavaScript / JS / 자바스크립트)

 

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

 

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

예제 입력

5
4 1 5 2 3
5
1 3 7 9 5

 

예제 출력

1
1
0
0
1

---

 

문제 접근

 

m_arr.forEach(m => {
    if(n_arr.includes(m)) result.push(1);
    else result.push(0);
});

 

위 코드처럼 단순히 n 배열과 m 배열을 모두 순회하는 간단한 방법으로도 구현할 수는 있지만,

forEach()와 include()는 선형 탐색 방법으로 각각 O(n)의 시간복잡도를 가지므로 위 코드의 시간복잡도는 O(n^2)가 된다.

 

 

문제에서 주어진 n과 m의 최댓값은 100,000이므로 최악의 경우 총 10,000,000,000번의 연산 -> 시간초과가 나온다.

 

시간을 줄이기 위해 Binary Search(이분 탐색)를 사용할 수 있다.

이분 탐색

- 정렬되어 있는 리스트에서 범위를 절반씩 줄여가며 탐색하는 방법

- start, end, mid를 사용하여 탐색한다. 찾으려는 값과 mid를 반복해서 비교한다.

 

정답 코드

//백준 1920번: 수 찾기

//입력
const input = require('fs').readFileSync('dev/stdin').toString().trim().split('\n');
const n_arr = input[1].split(' ').map(v=>+v);
const m_arr = input[3].split(' ').map(v=>+v);

n_arr.sort((a,b) => a - b); //탐색 대상 정렬

const result = [];

m_arr.forEach(m => { //m 배열 순회
    let start = 0;
    let end = n_arr.length - 1;
    let isNumberInArray = false; //m 요소가 n 배열에 있는지 판별하는 변수
    while(start <= end) {
        let mid = parseInt((start + end) / 2);
        if(m < n_arr[mid]) {
            end = mid - 1;
        }
        else if (m > n_arr[mid]) {
            start = mid + 1;
        }
        else { //m == n_arr[mid]
            isNumberInArray = true;
            break;
        }
    }
    if(isNumberInArray) result.push(1);
    else result.push(0);
});

console.log(result.join('\n'));

 

m 배열의 요소들을 순회하면서, 각각의 요소가 n 배열 안에 있는지 이분 탐색을 통해 검사한다.

//이분 탐색 부분

while(start <= end) {
        let mid = parseInt((start + end) / 2);
        if(m < n_arr[mid]) {
            end = mid - 1;
        }
        else if (m > n_arr[mid]) {
            start = mid + 1;
        }
        else { //m == n_arr[mid]
            isNumberInArray = true;
            break;
        }
    }

정렬된 n 배열의 탐색 범위를 계속해서 절반으로 줄여나가면 하나의 요소가 남을 때까지 절반으로 줄이는 과정을 반복하게 된다.

반복 중, 찾고자 하는 m 요소가 이분 탐색의 mid 지점에 해당한다면 탐색이 완료 및 중단된다.

위 알고리즘(이분 탐색)은 최악의 경우, start <= end라면 계속해서 탐색 범위를 절반으로 줄여야 하므로

시간복잡도는 O(logn)이 된다.

m 배열을 순회하는 시간복잡도는 O(n)이므로, 전체 시간복잡도는 O(nlogn)이 된다.

 

 

다른 방법

자바스크립트의 내장된 Set과 has()를 사용해서도 구현할 수 있다.

//백준 1920번: 수 찾기

//입력
const input = require('fs').readFileSync('dev/stdin').toString().trim().split('\n');
const n_arr = input[1].split(' ').map(v=>+v);
const m_arr = input[3].split(' ').map(v=>+v);

const n_set = new Set(n_arr); //집합으로 전환

const result = [];

m_arr.forEach(m => { //m 배열 순회
    if(n_set.has(m)){
        result.push(1);
    }
    else result.push(0);
});

console.log(result.join('\n'));

 

자바스크립트의 내장 객체 Set은 해시 테이블로 구현되어 있고 배열과 달리 순서(index)가 없다.

내장된 has() 메소드 또한 해시 테이블을 사용하기 때문에 평균 O(1)의 시간복잡도로 요소가 있는지 검사할 수 있다.

이렇게 구현하면 총 O(n)의 시간복잡도가 되고 시간이 좀 더 줄어드는 것을 확인할 수 있다.

 

 

이 문제처럼 순서가 필요하지 않고 단순히 존재하는지 확인이 필요할 때는 Set을 사용하는 것도 좋은 방법이다.

 

---

 

1920번: 수 찾기