[BOJ] 1920번 : 수 찾기

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;

int N, M; 
vector<int> v1; 
vector<int> v2; 
bool find_num(int& a) {
	int left = 0; 
	int right = N-1; 
	while (left <= right) {
		int mid = (left + right) / 2; 
		if (v1[mid] == a) return true;
		else if (v1[mid] < a) left = mid + 1;
		else right = mid - 1;
	}
	return false;
}
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N; 
	for (int i = 0; i < N; i++) {
		int x; 
		cin >> x; 
		v1.push_back(x);
	}
	sort(v1.begin(), v1.end());
	cin >> M; 
	for (int i = 0; i < M; i++) {
		int x;
		cin >> x; 
		v2.push_back(x); 
	}
	for (int i = 0; i < M; i++) {
		cout << find_num(v2[i]) << '\n';
	}
}

binary search를 이용해 답을 도출했다. binary search를 하기 위해서는 sort가 필수적이다. 따라서, sort(v1)을 이용해서 sorting 해주었다. 이후, binary search 함수를 만들어, 풀이를 진행하였다. 

while문에서 left <= right로 설정해야 하는데, 설정해야 하는데, left >= right로 잘못설정하였다는 점과 right = N- 1로 설정해야 하는데, N으로 설정해서, 오류가 일어났었다. 

 

2. solution 2 :

// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// http://boj.kr/0d0917e336ac4d709029df43a9127ace
#include <bits/stdc++.h>
using namespace std;
int a[100005];
int n;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for(int i = 0; i < n; i++) cin >> a[i];
  sort(a,a+n);
  int m;
  cin >> m;
  while(m--){
    int t;
    cin >> t;
    cout << binary_search(a, a+n, t) << '\n';
  }
}

STL에서 제공하는 binary_search 함수를 사용해 문제를 풀 수도 있었다. 이부분은 다음에 사용해야겠다. 

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x13/solutions/1920.cpp

basic-algo-lecture/0x13/solutions/1920.cpp at master · encrypted-def/basic-algo-lecture

 

 

3. solution 3 :

// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// http://boj.kr/e8e4c3e6a0f94f43bc21a192492c34a8
#include <bits/stdc++.h>
using namespace std;

int a[100005];
int n;

int binarysearch(int target){
  int st = 0;
  int en = n-1;
  while(st <= en){
    int mid = (st+en)/2;
    if(a[mid] < target)
      st = mid+1;
    else if(a[mid] > target)
      en = mid-1;
    else
      return 1;
  }
  return 0; // st > en일 경우 while문을 탈출
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for(int i = 0; i < n; i++) cin >> a[i];
  sort(a, a+n);
  int m;
  cin >> m;
  while(m--){
    int t;
    cin >> t;
    cout << BinarySearch(t) << '\n';
  }
}

 

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x13/solutions/1920_1.cpp

basic-algo-lecture/0x13/solutions/1920_1.cpp at master · encrypted-def/basic-algo-lecture