[백준] 1920번 : 수 찾기 | binary search (C++)

---

문제

---

풀이

C++ 내 내장되어 있는 binary_search( ) 함수를 이용해 풀이했다.

시간복잡도는 O(logn)으로 빠른 속도로 계산할 수 있다.

 

입력받는 정수의 범위가 2의 31승까지 이므로 long long으로 선언한다.

 

	int n, m;
	long long listnum, findnum;
    
        cin >> n;

 

 

vector을 이용해 입력받은 값을 저장한다.

 

 	vector<int> listv;

        for (int i = 0; i < n; i++) {
		cin >> listnum;
		listv.push_back(listnum);
	}

 

 

binary search는 가운데에 있는 값(중간 크기의 값)을 기준으로 정렬하기 때문에, 꼭 오름차순 혹은 내림차순으로 정렬해야 한다.

따라서, sort() 함수를 이용해 정렬한 후 bianry_search() 함수를 사용한다.

 

        binary_search(listv.begin(), listv.end(), findnum);

 

 

vector listv의 처음부터 끝까지 findnum이 있는지 확인하고 있으면 true, 없으면 false를 반환하는 코드이다.

 

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

	cin >> m;

	for (int i = 0; i < m; i++) {
		cin >> findnum;

		bool isFound = binary_search(listv.begin(), listv.end(), findnum);	// binary search를 사용할 때는 먼저 오름차순, 내림차순 정렬을 해줘야 함.
		// vector listv의 처음부터 끝까지 findnum이 있는지 확인하고 있으면 true, 없으면 false 반환
        cout << isFound << "\n";
	}

 

 

---

코드

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, m;
	long long listnum, findnum;
	vector<int> listv;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> listnum;
		listv.push_back(listnum);
	}

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

	cin >> m;

	for (int i = 0; i < m; i++) {
		cin >> findnum;

		bool isFound = binary_search(listv.begin(), listv.end(), findnum);	// binary search를 사용할 때는 먼저 오름차순, 내림차순 정렬을 해줘야 함.
		cout << isFound << "\n";
	}
	return 0;
}

---

결과

https://www.acmicpc.net/problem/1920

1920번: 수 찾기