[C++] 백준 1920번: 수 찾기

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

1920번: 수 찾기

풀이

sort를 통해 정렬되어있는 수들을 인덱스에 따라 이진탐색을 진행해 줍니다.

여기서 이진탐색을 재귀적으로 수행하게되면 시간초과가 발생하므로 whlie 루프를 활용하여 이진탐색을 진행합니다.

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

using namespace std;

vector<int>v;

void BS(int s, int e, int n) {
	int mid;
	while (e >= s) {
		mid = (s + e) / 2;
		if (v[mid] == n) {
			cout << 1 << '\n';
			return;
		}
		else if (v[mid] < n)
			s = mid + 1;
		else
			e = mid - 1;
	}
	cout << 0 << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int N, M, k;

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> k;
		v.push_back(k);
	}
	sort(v.begin(), v.end());

	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> k;
		BS(0, v.size() - 1, k);
	}

	return 0;
}

 

풀이2(정렬을 직접 병합정렬을 구현하여 진행)

#include <iostream>
#include <vector>

using namespace std;

int S[100001];

void merge(int low, int mid, int high) {
	vector<int>u;
	int i = low;
	int j = mid + 1;
    
	while (i <= mid && j <= high) {
		if (S[i] < S[j]) {
			u.push_back(S[i]);
			i++;
		}
		else {
			u.push_back(S[j]);
			j++;
		}
	}
	for (int t = j; t <= high; t++)
		u.push_back(S[t]);
	for (int t = i; t <= mid; t++)
		u.push_back(S[t]);
	for (int t = low; t <= high; t++)
		S[t] = u[t - low];
}

void mergeSort(int low, int high) {
	if (low < high) {
		int mid = (low + high) / 2;
		mergeSort(low, mid);
		mergeSort(mid + 1, high);
		merge(low, mid, high);
	}
}

void BS(int s, int e, int n) {
	int mid;
	while (e >= s) {
		mid = (s + e) / 2;
		if (S[mid] == n) {
			cout << 1 << '\n';
			return;
		}
		else if (S[mid] < n)
			s = mid + 1;
		else
			e = mid - 1;
	}
	cout << 0 << '\n';
}


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

	int N, M, k;
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> S[i];
	mergeSort(1, N);

	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> k;
		BS(1, N, k);
	}

	return 0;
}