[ boj : 20551 ] Sort 마스터 배지훈의 후계자

www.acmicpc.net/problem/20551

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

문제 : 배열 A가 주어지고 이를 정렬한 배열을 B라고 할때, 주어진 쿼리마다 각 값들이 B의 배열에서 어느 위치에 있는지 출력하여라

 

해설 : 요새 이분탐색 문제만 쉬운것 부터 풀고있는 중입니다.

A배열을 sort 한 후 이분탐색으로 위치를 찾아내면 됩니다. 그러나 '처음으로 등장한 위치'를 출력하여하기 때문에 low_bound가 되겠네요. 또한, 배열에 있지 않은 위치는 set을 사용해서 걸러주었습니다.

 

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int arr[200000];
set<int> s;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		s.insert(arr[i]);
	}
	sort(arr, arr + n);
	int x;
	for (int i = 0; i < m; i++) {
		cin >> x;
		if (s.find(x) == s.end()) {
			cout << -1 << "\n";
			continue;
		}
		int ans;
		int l = 0, r = n - 1;
		while (l <= r)
		{
			int mid = (l + r) / 2;
			if (arr[mid] < x)
				l = mid + 1;
			else {
				ans = mid;
				r = mid - 1;
			}
		}
		cout << ans << "\n";
	}
	return 0;
}