<Baekjoon> #1920 Binary Search, Hash_수 찾기 c++ (Hash Table vs Binary Search Table)

#1920 수 찾기

풀이1 - Hash

• unordered_map<int, bool> map;을 만들어주고

scanf_s("%d", &x);
map[x] = true;

이렇게 숫자를 하나씩 받을 때마다 해당 숫자에 true를 저장해준다

• 두 번째로 숫자를 받아올 때 이 값이 hash map에 저장된 값이 맞다면 1, 아니라면 0을 print한다.

scanf_s("%d", &y);
if (map[y]) printf("1\n");
else printf("0\n");

#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
	int n, m;

	unordered_map<int, bool> map;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x;
		scanf_s("%d", &x);
		map[x] = true;
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		int y;
		scanf_s("%d", &y);
		if (map[y]) printf("1\n");
		else printf("0\n");
	}
	return 0;
}

처음 cin, cout 사용 했을 때는 시간 초과가 났고 scanf, printf 사용했을 때는 8016KB, 96ms

풀이2 - Binary Search

• 숫자들을 받아와 vector<int> num에 하나씩 push해주고 sort를 해준다.

• binary search함수를 만들어 target인 m을 찾는다

  low, high, target 세 변수를 두고 mid=low+high/2 를 통해 num[mid]가 target보다 작으면 mid+1~high 범위에서 재탐색하고, target보다 크면 low~mid-1에서 재탐색 한다.

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

const int MAX = 100000;
int N, M;
vector<int> num;
int binarySearch(int low, int high, int target){
  if (low > high)
      return 0;
  else {
      int mid = (low + high) / 2;
      if (num[mid] == target)
          return 1;
      else if (num[mid] > target)
          return binarySearch(low, mid - 1, target);
      else
          return binarySearch(mid + 1, high, target);
  }
}

int main(void){
  ios_base::sync_with_stdio(0);
  cin.tie(0); 
  cin >> N;
  for (int i = 0; i < N; i++)  {
      int x;
      cin >> x;
      num.push_back(x);
  }
  sort(num.begin(), num.end());
  cin >> M;
  for (int i = 0; i < M; i++) {
      int y;
      cin >> y;
      cout << binarySearch(0, N - 1, y) << "\n"; 
  }
  return 0;
}

이렇게 했을 때는 메모리와 시간이 2916KB , 56ms였다

• Hash Table vs Binary Search

  당연히 Hash는 O(1), binary search는 O(longN)의 시간복잡도를 가지니 hash가 빠를거라고 생각했는데 위와 같이 범위 내에서 search 연산을 수행하는 경우 bst가 빠르고, 또 만약 문제에서 라이브러리를 추가하는 것을 허용하지 않는 경우 bst로 풀었어야 했다.

  그리고 몇 가지 참고 될만한 자료
  
  
  참고1 참고2