문제
입출력
문제 요약
6 | 3 | 2 | 10 | -10 |
이렇게 입력 값이 주어진다면
10 | 9 | -5 | 2 | 3 | 4 | 5 | -10 |
위 배열이 입력 값에 포함된다면 1출력 아니면 0을 출력하면 된다.
단순하게 2중 반복문으로 탐색을 할 순 있지만
카드의 수가 500,000개로 (n)^2이면 시간제한에 넘기 때문에 이진 탐색으로 풀어야한다는 걸 알 수 있다.
1. 이진 탐색은 정렬이 필수적으로 필요하기 때문에 입력 배열을 정렬한다.
-10 | 2 | 3 | 6 | 10 |
이 배열을 갖고 입력값마다 존재한지 아닌지를 판단해주면 된다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N, M, temp;
vector<int> v1;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> temp;
v1.push_back(temp);
}
sort(v1.begin(), v1.end());
cin >> M;
for (int i = 0; i < M; i++) {
cin >> temp;
cout << binary_search(v1.begin(), v1.end(), temp) << " ";
}
return 0;
}
'📖Algorithm > Binary Search' 카테고리의 다른 글
자바 [Algorithm] 이분탐색 - 백준 20444 색종이와 가위 (0) | 2024.06.06 |
---|---|
자바 [Algorithm] 이분탐색 - 백준 11687 팩토리얼 0의 개수 (0) | 2024.06.05 |
자바 [Algorithm] 이분탐색 - 백준 1920 수 찾기 (1) | 2024.06.02 |
자바 [Algorithm] 이분탐색 - 백준 10815 숫자 카드 (0) | 2024.06.01 |
자바 [Algorithm] 이분탐색 - 백준 4158 CD (0) | 2024.05.31 |