#1920 수 찾기

# 문제

# 입력 및 출력

# 풀이

처음에 완전 간단하다고 생각했음ㅋㅋㅋ

배열 크기를 100,001로 선언해놓고 인덱스에 맞게 숫자를 넣어서(4면 인덱스4번에 저장) 4번째줄에 입력받는 수들을 인덱스로 접근해서 있는지 확인하려고 했었다

말이 좀 어려운데 예제를 예로 들면 배열에 인덱스 1에 1, 인덱스 2에 2, 인덱스 3에 3 ... 이런식으로 저장해놓고 밑에서 입력받은 수 1, 3, 7, 9, 5를 배열[1], 배열[3], 배열[7], 배열[9], 배열[5] 이런 식으로 접근해서 값이 있는지 확인하는 식으로 코드를 짰는데 보니까 입력 받는 수의 개수가 100,000개인거고 수의 크기는 int형 범위크기라 배열이 int 범위만큼 필요했었던거다,, 그래서 채점하는데 컴파일 에러 발생,,ㅎ

 

그래서 밑에 알고리즘 분류를 보니까 이분탐색으로 풀라고 되어있더라

이분탐색 코드 구글링했음,,ㅋㅋ

근데 계속 시간초과 뜨더라;;

 

왜그런지 찾아보니까 cin, cout가 원인인 경우가 많더라

ios::sync_with_stdio(0); 
cin.tie(0);
cout.tie(0);

그래서 위 코드를 넣어줬는데도 시간 초과;

 

또 찾아보니까 endl이 부하가 걸리는 경우가 많대서 "\n"으로 바꿔줬더니 돌아가더라,,

#include <iostream>
#include <algorithm>
using namespace std;
int arr[100001];
int n, m;

void bin(int t) {
	int start = 0;
	int end = n - 1;
	int mid = (start + end) / 2;
	while (start <= end) {
		if (arr[mid] == t) {
			cout << 1 << "\n";
			return;
		}
		else if (arr[mid] < t) start = mid + 1;
		else end = mid - 1;
		mid = (start + end) / 2;
	}
	cout << 0 << "\n";
	return;
}

int main() {
	ios::sync_with_stdio(0); 
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + n);
	cin >> m;
	for (int i = 0; i < m; i++) {
		int t;
		cin >> t;
		bin(t);
	}
}

 

이분탐색은 이해했음,,

cin, cout말고 scanf, printf로 돌려봤는데 뭔가 이상한지 계속 에러떠서 그냥 원래 코드대로 쓰기로 함ㅋㅋ

 

무지성으로 계속 돌려서 온갖 에러는 다나왔음ㅋㅋ