테스트 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;
}
'알고리즘' 카테고리의 다른 글
[코드업] 3736 - LIS (Large) (0) | 2020.03.29 |
---|---|
[코드업] 3710 - 369 게임 3 (Large Test Case) (0) | 2020.03.28 |
[코드업] 3733 - 우박수 길이 (3n+1) (large) (1) | 2020.03.28 |
[코드업] 3007 - 기억력 테스트 7 (0) | 2020.03.28 |
[코드업] 2033 - 사다리 게임 (0) | 2020.03.28 |