[백준OJ] 20551번 SORT마스터 배지훈의 후계자

www.acmicpc.net/problem/20551

20551번: Sort 마스터 배지훈의 후계자

---

 

-풀이-

모두 c++에서 제공해주는 함수를 이용할것이다.

algorithm헤더에 있는 sort함수를 이용해 입력받은 배열을 정렬한 뒤, lower_bound를 이용하여, 같거나 큰 숫자중 제일 먼저나오는 수를 검색한다.

그런다음 그 ind의 원소가 찾고싶어하는 숫자인지 비교하여 맞으면 ind출력, 아니면 -1을 출력한다.

 

-시간복잡도-

정렬은 퀵소트를 이용하므로 O(NlogN) , 이분탐색도 O(LogN)으로 동작하는 함수이므로, O(MlogN)이 걸린다.

M과 N의 범위가 같으므로 시간복잡도는 O(NlogN) 또는 O(MlogN)이 걸린다

 

-코드-

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

vector<int> v;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	cin >> n>>m;
	for (int i = 0; i < n; i++) {
		int data;
		cin >> data;
		v.push_back(data);
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < m; i++) {
		int f;
		cin >> f;
		
		int ind = lower_bound(v.begin(), v.end(), f) - v.begin();
		if (ind!=n&&v[ind] == f) {
			cout << ind << "\n";
		}
		else {
			cout << "-1\n";
		}
	}
	return 0;
}