상세 컨텐츠

본문 제목

백준 2776 : 암기왕 C++

cote/Intermediate

by geminanolja 2025. 1. 6. 18:40

본문

문제

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

 

두 vector에 숫자들을 저장하고 b배열에 있는 숫자들이 a에 있으면 1을 출력하고 없으면 0을 출력하기

이렇게 문제를 풀기로 했다.

 

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

vector<int> a,b;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n,m,o;

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> m;
		a.resize(m);
		for (int i = 0; i < m; i++)
		{
			cin >> a[i];
		}
		//for (auto v : a) cout << v << " ";
		cout << endl;

		//정렬 (이진 탐색을 위해  꼬오옥 필요!)
		sort(a.begin(), a.end());

		cin >> o;
		b.resize(o);
		for (int i = 0; i < o; i++)
		{
			cin >> b[i];
		}
		//for (auto v : b) cout << v << " ";
		cout << endl;

		for (int i = 0; i < o; i++)
		{
			if (binary_search(a.begin(), a.end(), b[i]))
			{
				cout << 1 << "\n";
			}
			else
			{
				cout << 0 << "\n";
			}
		}
	}
	return 0;
}

 

처음엔 for문으로 다 돌릴려고 했는데 시간초과가 떴다

 


			auto it = find(a.begin(), a.end(), b[i]);
			if (it != a.end())
			{
				cout << 1 << "\n";
			}
			else
			{
				cout << 0 << "\n";
			}

 

그래서 a배열을 sort로 정렬하고 binary search로 동일하게 구현

다행히 시간초과도 통과!

관련글 더보기