본문 바로가기

알고리즘

[코드업] 3020 - 기억력 테스트 4

테스트 3을 무사히 마친 주현이는 테스트 4에 도전하게 되었다.

주현이 엄마는 이번에 무작위로 숫자 N개를 불러준다음, M개의 질문을 하기로 했다.

질문으로 그 숫자가 있었으면 그 숫자를 몇 번째로 불렀는지 출력하고, 없었다면 -1을 출력한다.

이 테스트에는 주현이가 좋아하는 '또봇 X, Y, Z'가 걸려있다.

주현이를 도와줄수 있는 프로그램을 만드시오.

입력

첫째줄에 N이 입력된다. (1 <= N <= 1,000,000)

둘째 줄에 N개의 서로 다른 숫자가 공백으로 구분되어  입력된다. ( 데이터값의 범위 : 1 ~ 100,000,000)

셋째줄에 질문의 수 M이 입력된다. ( 1 <= M <= 100,000)

넷째 줄에 M개의 질문이 입력된다

출력

M개의 질문에 대해 그 숫자가 있었으면 그 숫자를 몇 번째로 불렀는지를 출력, 없었으면 -1을 하나씩 차례대로 출력한다.

더보기

입력 예시   예시 복사

5
23 5 32 87 50
4
5 2 100 87

출력 예시

2 -1 -1 4


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

vector<pair<int, int>> vec;

int binarySearch(int start, int end, int search){
	if(start > end) return -1;

	int mid = (start + end) / 2;
	if(vec[mid].first == search) return vec[mid].second;
	if(vec[mid].first > search)
		return binarySearch(start, mid - 1, search);
	else if(vec[mid].first < search)
		return binarySearch(mid + 1, end, search);
}

int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
    
	int N;
	cin >> N;
	vec.resize(N);

	int num;
	for(int i = 0; i < N; i++){
		cin >> num;
		vec[i] = { num, i + 1 };
	}

	sort(vec.begin(), vec.end());

	int M;
	cin >> M;

	int query;
	while(M--){
		cin >> query;
		cout << binarySearch(0, N - 1, query) << " ";
	}
	return 0;
}