푸키키키

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

let a = [];
let b = [];
let z;
const bs = (left, right) => {
  const mid = Math.floor((left + right) / 2); 
  if(left > right) {
    return 0;
  }
  let tval = a[mid]; 
  if(tval > z) {
    return bs(left, mid-1);
  } else if(tval < z){
    return bs(mid+1, right);
  } else {
    return 1;
  }
}

for(let i=0;i<Number(input[0]);++i) {
  a = input[i*4+2].split(' ').map(x => parseInt(x));
  b = input[i*4+4].split(' ').map(x => parseInt(x));
  a.sort();
  for(const v of b) {
    z = v;
    console.log(bs(0, Number(input[i*4+1]-1)));
  }
}

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int arr[1000010];
int cmp;
int bs(int left, int right) {
  int mid = (left + right) / 2;
  if(left > right) {
    return 0;
  }
  int tval = arr[mid];
  if(tval > cmp) {
    return bs(left, mid-1);
  } else if(tval < cmp) {
    return bs(mid+1, right);
  } else {
    return 1;
  }
}

int main(void) {
  int t;
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  cin >> t;
  while(t--) {
    int a, b;
    cin >> a;
    for(int i=0;i<a;++i) {
      cin >> arr[i];
    }
    sort(arr,arr+a);
    cin >> b;
    for(int i=0;i<b;++i) {
      cin >> cmp;
      cout << bs(0,a-1) << '\n';
    }
  }
}

js로 똑같이 구현해도 시간초과가 났다. 질의응답에서 데이터 입력이 많아 입력속도가 중요하다고 하는데 javascript로 어떻게 올려야 할지 모르겠다.

개요

보통 자주 사용하는 body-parser나 morgan등 예제 코드를 통해

app.use( ... ) 

...에 적용할 미들웨어를 넣으면 이렇게 body-parser나 morgan 같은 라이브러리가 적용되는 마법같은 것으로 알고 있었다. 이번에 공부를 해서 마법이 아니라 기술로 만들어 보고자 한다.
(모르면 마법, 알면 기술 - 이고잉)

미들웨어의 매우 간단한 의미

만약 만든 서버에서 접속을 하면 반드시 A기능과 B기능을 실행해야 한다고 가정하자.

미들웨어를 사용하지 않으면

app.get('/', (req, res) => {
  console.log("A 기능 실행");
  console.log("B 기능 실행");
  console.log("다음 동작");
})

app.get('/hello', (req, res) => {
  console.log("A 기능 실행");
  console.log("B 기능 실행");
  console.log("다음 동작 hello");
})

...

모든 라우터마다 위와 같이 A기능과 B기능을 실행하는 코드를 위에 적어줘야 한다.

미들웨어를 사용하면

app.use((req, res, next) => {
  console.log("A 기능 실행");
  next();
})

app.use((req, res, next) => {
  console.log("B 기능 실행");
  next();
})

app.get('/', (req, res) => {
  console.log("다음 동작");
})

app.get('/hello', (req, res) => {
  console.log("다음 동작 hello");
})

위와 같이 app.use를 통해 app.get ... 라우터 실행 전에 수행해야할 동작을 미리 지정해 두어 훨씬 깔끔하게 코드 작성이 가능해진다.

좀 더 구체적인 미들웨어

참고 : https://expressjs.com/en/guide/using-middleware.html

미들웨어는 총 5가지 타입으로 나뉜다.

• Application-level middleware
• Router-level middleware
• Error-handling middleware
• Built-in middleware
• Third-party middleware

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

const bs = (left, right, z) => {
  const mid = Math.floor((left + right) / 2); 
  if(left >= right) {
    return mid;
  }
  let tval = Math.floor(((Y + mid) / (X + mid))* 100);
  if(tval > z) {
    return bs(left, mid, z);
  } else {
    return bs(mid+1, right, z);
  }
}

let a = input[0].split(' ');
const X = Number(a[0]);
const Y = Number(a[1]);
const Z = Math.floor((100 * Y / X));
let result = 0;
result = bs(0, 100000000001, Z);
if(result == 100000000001) {
  result = -1;
}
console.log(result);

풀이

Lower bound 알고리즘으로 풀 수 있었다.이분 탐색이랑 유사하지만 조건 만족할 때에는 mid를 증가시키지 말고 만족 안할 때 mid를 증가시켜 탈출 조건에서 조건 만족시켰던 것 중 가장 먼저 나오는 답을 return 한다.

문제였던 것

// 입력 X = 50, Y = 29 일때
console.log(100 * Y / X);
console.log(Y / X * 100)

//output
58
57.999999999...

위와 같이 차이가 있었다.