1920: 수 찾기

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

1920번: 수 찾기

설명

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X 라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

핵심 아이디어

• N개의 정수에서 X가 있는지 탐색하는 문제이다. N의 최대가 100,000이기 때문에 2중 for문을 사용하면 시간초과 발생한다. 따라서 규모가 큰 데이터에서 target 값을 찾기 수월한 이진 탐색 을 사용하자. 이진 탐색의 시간 복잡도는 O(logN)을 보장하며, 반드시 정렬된 상태에서 사용해야 한다. 

코드 구현

C++

해당 코드는 이진 탐색을 직접 구현해서 풀이 한것이다. 

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

int n;
vector<int> arr;

int m;
vector<int> ans;

int binarySearch(vector<int>& arr, int start, int end, int target) {
	int mid;
	while (start <= end) {
		mid = (start + end) / 2;
		if (arr[mid] == target) {
			return 1;
		}
		else if (arr[mid] > target) end = mid - 1;
		else if (arr[mid] < target) start = mid + 1;
	}
	return 0;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		arr.push_back(num);
	}

	sort(arr.begin(), arr.end());
	cin >> m;
	
	while (m--) {
		int target;
		cin >> target;

		int result;
		result = binarySearch(arr, 0, n - 1, target);
		ans.push_back(result);
	}

	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << "\n";
	}
}

해당 코드는 이진 탐색 기능을 가져와서 사용한 것!

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

int n; // 자연수 n
vector<int> arr; // 자연수 입력 받기
int m; // target 개수
vector<int> ans; // 결과를 저장할 벡터

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		arr.push_back(num);
	}
	// 이진 탐색을 위해 정렬한다.
	sort(arr.begin(), arr.end());
	cin >> m;
	while (m--) {
		int target;
		cin >> target;

		if (binary_search(arr.begin(), arr.end(), target)) {
			ans.push_back(1);
		}
		else {
			ans.push_back(0);
		}
	}
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << "\n";
	}
	return 0;
}