글 읽기 - 10816 숫자카드2 어떤부분에서 시간초과가 발생할까요?

moona0115 2년 전 0

시간초과가 발생할만한 부분을 못찾겠습니다.

sort -> upper_bound -> lower_bound 순으로 찾는데, 계속해서 시간초과가 뜨네요..

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

int binary_S(vector<int> v, int key) {
	int start, end, mid, cnt = 0, temp;
	start = 0;
	end = v.size() - 1;

	while (start <= end) {
		mid = (start + end) / 2;
		if (v[mid] < key) {
			start = mid + 1;
		}
		else {
			end = mid - 1;
		}
	}
	temp = start;

	if (v[temp] != key) return 0;

	start = 0;
	end = v.size() - 1;

	while (start <= end) {
		mid = (start + end) / 2;
		if (v[mid] <= key) {
			start = mid + 1;
		}
		else {
			end = mid - 1;
		}
	}
	
	return (end - temp + 1);
}


int main() {
	int n, m, x;
	scanf("%d", &n);
	vector<int> v(n);
	
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &v[i]);
	}
	sort(v.begin(), v.end());

	scanf("%d", &m);
	
	for (int i = 0; i < m; i++)
	{
		scanf("%d", &x);
		int k = binary_S(v, x);
		printf("%d ", k);
	}

	
	return 0;
}

djm03178 2년 전 1

binary_S 함수에서는 vector를 값으로 받고 있어, 함수를 호출할 때마다 벡터의 모든 내용이 복사되어 새로운 벡터가 만들어집니다.

moona0115 2년 전 0

감사합니다.

부족한 제 수준에서는

첫번째, vector를 이용하지 않는 방법

두번째, upper_bound, lower_bound를 사용하는 방법

정도가 있는것 같은데요, vector를 활용해서 함수를 만들어낼 수 있는 방법은 없을까요?

djm03178 2년 전 0

참조자에 대해 알아보세요.

moona0115 2년 전 0

넵 많은도움이 되었습니다 감사합니다

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

문제

문제

출처

ICPC

10816 숫자카드2 어떤부분에서 시간초과가 발생할까요?

moona0115 2년 전 0

djm03178 2년 전 1

moona0115 2년 전 0

djm03178 2년 전 0

moona0115 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말