[baekjoon] 1920 수찾기 (Javascript, c++)

1920번: 수 찾기 (acmicpc.net)

1920번: 수 찾기

---

접근 방법

알고리즘 : Binary Search

 

1. Brute force로 풀면 1억번이 넘어가는 연산으로 O(N^2)의 시간복잡도를 가진다.

2. Binary Search를 통해 O(NlogN)으로 푼다.

 

c++은 STL로 Binary Search를 제공한다.

재귀를 활용한 방법으로 직접 구현 및 STL을 활용했다.

 

// Javascript는 Binary Search를 사용해도 시간초과 => set을 활용한 방법으로 풀이를 참고했다.

---

Javascript

const fs = require('fs');
const input = fs.readFileSync('./dev/stdin').toString();
const [N, nums1, M, nums2] = input.split('\n');
const set = new Set(nums1.split(' '));
const numArr = nums2.split(' ');
const result = [];
for (let i = 0; i < numArr.length; i++) result[result.length] = set.has(numArr[i]) ? 1 : 0;
console.log(result.join('\n'));

 

---

C++

#include <bits/stdc++.h>
using namespace std;

    //binary_search
    bool binarySearch(vector<int>& arr, int low, int high, int target){
      if(low>high) return false;
      int mid = (low+high)/2;

      if(arr[mid]==target) {
        return true;
      }
      if(arr[mid]>target){
        return binarySearch(arr,low,mid-1,target);
      } else {
        return binarySearch(arr,mid+1,high,target);
      }
    }

int main()
{
  freopen("input.txt", "r", stdin); //제출 시 삭제

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //input
    int n,m;
    cin>>n;
    vector<int> v(n);

    for(int i=0;i<n;i++) cin>>v[i];
    
  sort(v.begin(),v.end());



    cin >>m;
    //check
    for(int i=0;i<m;i++){
      int check;
      cin>>check;

      //STL binary_search(v.begin(),v.end(),check) => true,false
      if(binarySearch(v,0,n-1,check)){ 
        cout<<1<<"\n";
      } else {
        cout<<0<<"\n";
      }


    };
    
  return 0;

  

}