글 읽기 - [시간초과] 질문합니다

cjswodmlskfk 4년 전 1

시간초과가 나서 질문합니다

1. stl sort를 사용해서 comparer 의 문제는 없다고 생각했습니다.

2. left <= right 조건을 지켜서 left == right 일 때도 작동되게 만들었습니다.

혹시 이 외에 이 문제를 시간초과 나지 않도록 해야 하는 포인트가 또 있을까요?

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>

//namespaces
using namespace std;

//variables
int N, M;
int  * A;

//main method
int main() {

	cin >> N;
	A = new int[N];

	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	//stl sort
	sort(A, A + N);
	
	cin >> M;
	int temp;
	for (int i = 0; i < M; i++) {
		cin >> temp;

		//binary search
		int left = 0;
		int right = N - 1;
		int middle;
		bool flag = false;
		while (left <= right) {
			middle = (left + right) / 2;
			if (A[middle] == temp) {
				flag = true;
				break;
			} else if (A[middle] < temp) {
				left = middle + 1;
			} else if (A[middle] > temp) {
				right = middle - 1;
			}
		}

		if (flag) {
			cout << 1 << "\n";
		} else {
			cout << 0 << "\n";
		}

	}

	return 0;
}

lovinix 4년 전 1

빠른 입출력을 사용해보세요

https://www.acmicpc.net/problem/15552

cjswodmlskfk 4년 전 0

int main (){
// speed reading

cin.tie(NULL);

ios_base::sync_with_stdio(false);

으로 해결했습니다. 입출력에 문제가 될 줄은 몰랐네요. 감사합니다.

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

문제

문제

출처

ICPC

[시간초과] 질문합니다

cjswodmlskfk 4년 전 1

lovinix 4년 전 1

cjswodmlskfk 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말