[백준] 10815숫자카드 c++

 

알고리즘 분류는 이분탐색으로 되어있는데 이분탐색으로 안풀고 이렇게 풀어도 될것같아서 이렇게 풀어봤다.

숫자가 마이너스도 들어오기 때문에 배열을 두개 만들어 주었고 들어온 숫자랑 똑같은 인덱스를 체크해주었다.

내일 이분탐색으로도 풀어봐야겠다.

#include<iostream>

using namespace std;

bool num[10000000];
bool Mnum[10000000];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int m,temp;
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> temp;
		if (temp < 0)
			Mnum[-(temp)] = true;
		else
			num[temp] = true;
	}
	int n,temp2;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> temp2;
		if (temp2 < 0)
			cout << Mnum[-(temp2)] << " ";
		else
			cout << num[temp2] << " ";
	}


	
}

이분탐색으로 다시 풀어봤다.

가질수 있는 숫자카드의 범위를 전부 배열로 만들어 둘 필요가 없고

가지고 있는 숫자 카드 값을 벡터에 저장하면된다.

가지고 있는 숫자카드 벡터를 정렬해주고 새로들어오는 숫자가 있는지 이분탐색을 통해 확인해주면 된다.

이 방법으로 풀어도

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

이거 안적어주면 시간초과가 난다.

그리고 left =mid+1 이라고 해야하는데 left=mid 이런식으로 해서 무한루프에 빠졌었다.

다음엔 꼭 조심해야겠다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

vector<int>num;


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m, temp;
	cin >> n;
	
	for(int i=0;i<n;i++)
	{ 
		cin >> temp;
		num.push_back(temp);
	}
	sort(num.begin(), num.end());

	cin >> m;
	int right, left, mid;
	bool check = false;
	while (m--)
	{
		cin >> temp;
		right = n-1;
		left =0;
		//cout << left << "   " << right;
		
		check = false;
		while (right >= left)
		{
			mid = (right + left) / 2;
			//cout << left<<"  " << right << endl;
			if (temp > num[mid])
				left = mid +1;
			else if (temp < num[mid])
				right = mid-1;
			else
			{
				cout << 1 << " ";
				check = true;
				break;
			}
				
		
		}
		if (!check)
			cout << 0 << " ";

	}
}