글 읽기 - 이진탐색, STL sort 시간초과 질문

quffl9612 4년 전 0

이전에 C언어로 직접 Quick sort와 Binary Search를 구현해서 풀었을때는 맞았는데,

C++로 다시해보니 시간초과가 뜨네요... cin, cout 에 별다른 설정이 필요한가요...?

도움주시면 감사하겠습니다 ㅠㅠ

#include <iostream>
#include <algorithm>

using namespace std;

int n, m, n_container[100001];

int solve(int start, int end, int target) {
	if (start > end) return 0;
	int medium = (start + end) / 2;
	if (n_container[medium] == target) return 1;
	else if (n_container[medium] > target) return solve(start, medium - 1, target);
	else return solve(medium + 1, end, target);
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> n_container[i];
	}
	sort(n_container, n_container + n);
	cin >> m;
	int temp;
	for (int i = 0; i < m; i++) {
		cin >> temp;
		if (temp < n_container[0] || temp > n_container[n - 1])
			cout << 0 << endl;
		else
			cout << solve(0, n - 1, temp) << endl;
	}
	return 0;
}

bupjae 4년 전 0

cin 과 cout 를 번갈아가며 쓸 경우에는 매번 buffer flush 가 발생합니다.

buffer flush 는 시간이 많이 걸리는 연산으로, interactive 문제 이외의 문제에서는 별 의미가 없습니다.

buffer flush 기능을 끄기 위해서는 main 맨 앞에 cin.tie(nullptr); 를 사용하면 됩니다.

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

문제

문제

출처

ICPC

이진탐색, STL sort 시간초과 질문

quffl9612 4년 전 0

bupjae 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말