풀이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
였다