글 읽기 - 시간 초과 이유 알고싶습니다.(코드주석첨부)

tigger97 4년 전 1

코드에 주석은 첨부하였습니다.

시간초과라고 나는데 이유를 모르겠습니다.

n과 m에 각각 10만이 입력되면 ,

for문 안에서 m이 10만번, 이진탐색하는데log2(100000)이니 100000*log2(100000)=대략 16만이 나와서 시간초과가 안되는 것 같은데

어디서 오류인지 궁금합니다.

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

int main() {
	int n, m;
	cin >> n;
	int* a = (int*)malloc(sizeof(int)*n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	cin >> m;
	int* b = (int*)malloc(sizeof(int) * m);
	for (int i = 0; i < m ; i++) {
		cin >> b[i];
	}//입력된 두 파트를 각각 배열 a와, 배열 b에 받는다.
	
	for (int i = 0; i < m; i++) {
		bool chk = false;//같은수가 있는지 확인하는 bool값입니다.
		int left = 0, right = n - 1;
		long long int mid;//left+right가 21억을 초과할 때를 대비하여 longlong으로 해줬습니다.
		while(left <= right){//while문은 이진탐색부분입니다.
			mid = (left + right) / 2;
			if (b[i] == a[mid]) {
				chk = true;
				break;
			}
			else if (b[i] < a[mid]) {
				right = mid - 1;
			}
			else if (b[i] > a[mid]) {
				left = mid + 1;
			}
		}
		if (chk == true) {//chk가 true이면 값이 있으므로 1출력
			cout << "1" << endl;
		}
		else if (chk == false) {//없으면 0출력
			cout << "0" << endl;
		}
	}

}

djm03178 4년 전 1

https://www.acmicpc.net/proble...

tigger97 4년 전 0

감사합니다!!!

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

문제

문제

출처

ICPC

시간 초과 이유 알고싶습니다.(코드주석첨부)

tigger97 4년 전 1

djm03178 4년 전 1

tigger97 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말