글 읽기 - 이분탐색, flush문제 아닌데 시간초과입니다 ㅠㅠ

choidlswp 4년 전 0

흔히 하는 실수인 cin, cout의 flush 문제나 이분탐색 end 값을 N-1로 세팅하는 부분 다 신경써서 코드를 짰는데 계속 시간 초과가 나옵니다 ㅠㅠ
코드 중에 어디가 문제인지 알려주시면 대단히 감사드리겠습니다!!!

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

void BinarySearch(vector<int> arr, int start, int end, int key) {
  int mid = (start + end) / 2;

  if (arr[mid] == key) {
    cout << "1" << "\n";
    return;
  }

  if (start > end) {
    cout << "0" << "\n";
    return;
  }

  if (arr[mid] > key)
    BinarySearch(arr, start, mid-1, key);

  else if (arr[mid] < key)
    BinarySearch(arr, mid+1, end, key);

}

int main(int argc, char const *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  vector<int> v;
  int num, src;
  
  int N; cin >> N;
  for (int i = 0; i < N; i++) {
     cin >> num;
     v.push_back(num);
  }

  sort(v.begin(), v.end());

  int M; cin >> M;
  for (int i = 0; i < M; i++) {
    cin >> src;
    BinarySearch(v, 0, N-1, src);
  }

  return 0;
}

djm03178 4년 전 1

vector를 값으로 넘겨주면 호출할 때마다 내용물이 전부 복사되어 새로운 vector가 만들어지기 때문에 매우 느립니다. 이럴 때 참조자를 써야 합니다.

choidlswp 4년 전 0

와... 복사가 되어버리는줄은 상상도 못했습니다.. 벡터 공부 더 열심히 하고 오겠습니다! 감사합니다!!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이분탐색, flush문제 아닌데 시간초과입니다 ㅠㅠ

choidlswp 4년 전 0

djm03178 4년 전 1

choidlswp 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말