[C++]백준 - 1920번 문제

1920번: 수 찾기 (acmicpc.net)

1920번: 수 찾기

 

1920번 : 수 찾기

---

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

 

 

출력

---

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

 

 

---

 

생각해 볼 점

---

이분 탐색의 기초 문제

정렬 후 이분 탐색합니다.

 

cout과 cin을 그냥 사용하면 시간 초과가 날 수 있으므로 주의합니다.

 

코드

---

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

int main() {
	int N, M;
	vector<int> v;
	scanf("%d", &N);
	for(int i = 0; i < N; i++)
	{
	    int input;
	    scanf("%d", &input);
	    v.push_back(input);
	}
	sort(v.begin(), v.end());    //정렬
	scanf("%d", &M);
	for(int i = 0; i < M; i++)
	{
	    int target;
	    scanf("%d", &target);
	    int left = 0;
	    int right = N;
	    int is_exist = 0;
	    while(true)
	    {
	        int index = (right + left) / 2;    //이분탐색
	        if(v[index] == target)
	        {
	            is_exist = 1;
	            break;
	        }
	        else if(index == left) break;
	        else if(v[index] < target) left = index;
	        else right = index;
	    }
	    printf("%d\n", is_exist);
	}
	return 0;
}

 

그 외

---