글 읽기 - 시간초과 질문드립니다! c++

yjjj98 3년 전 0

계속 시간초과로 인해서 틀리는데 혹시 어디서문제인지 알려주신다면 정말 감사합니다!

#include<iostream>

using namespace std;
int binarySearch(int arr[], int start, int end, int target);
int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int a, arr[1000], start = 0, end, result, b, target[100000], targetpoint, temp = 0, count[1000] = {0,};
	cin >> a;
	end = a - 1;
	for (int i = 0; i < a; i++) {
		cin >>	arr[i];
	}
	for (int i = 0; i < a; i++) {
		for (int j = i; j < a; j++) {
			if (arr[i] > arr[j]) {
				temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
	}

	cin >> b;
	for (int i = 0; i < b; i++) {
		cin >> target[i];
	}
	
	for (int i = 0; i < b; i++) {
		targetpoint = target[i];
		result = binarySearch(arr, start, end, targetpoint);
		if (result != -1) {
			count[i] = 1;
		}
		else if (result == -1) {
			count[i] = 0;
		}
		start = 0, end = a - 1;
	}
	for (int i = 0; i < b; i++) {
		cout << count[i] << "\n";
	}

	return 0;
}
int binarySearch(int arr[], int start, int end, int target)
{
	int mid;
	mid = (start + end) / 2;
	if (start > end) {
		return -1;
	}
	else if (start == end) {
		if (arr[start] == target) {
			return start;
		}
		else
			return -1;
	}
	else {
		if (arr[mid] == target) {
			return mid;
		}
		else if (arr[mid] > target) {
			end = mid - 1;
			binarySearch(arr, start, end, target);
		}
		else if (arr[mid] < target) {
			start = mid + 1;
			binarySearch(arr, start, end, target);
		}
	}


}

djm03178 3년 전 0

67, 71번째 줄 이후에도 return값이 있어야 합니다.

yjjj98 3년 전 0

그래도 시간초과가 나네요 ,,,

djm03178 3년 전 0

arr과 count의 크기도 너무 작고, 정렬이 버블 정렬이어서 O(n^2)으로 너무 느립니다.

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

문제

문제

출처

ICPC

시간초과 질문드립니다! c++

yjjj98 3년 전 0

djm03178 3년 전 0

yjjj98 3년 전 0

djm03178 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말