10815 숫자 카드
https://www.acmicpc.net/problem/10815
◆ 문제 풀이
배열 두개를 입력받아, 뒤에 입력받은 배열의 숫자가 앞 배열에 포함되어있을 경우 1을, 아닐 경우 0을 출력하는 문제입니다.
■ 시간 초과가 핵심
간단한 방법 = 선형 탐색으로는 문제의 시간 제한을 통과할 수 없으므로, 시간을 단축할 방법을 찾아야 합니다.
■ 선형 탐색보다 이진 탐색이 빠름
가장 대표적인 해결책은 선형 탐색이 아닌 이진 탐색을 이용하여 탐색 시간을 단축하는 것입니다.
■ 이진 탐색을 위한 정렬 필요
이진 탐색을 위해서는 탐색 대상 배열이 정렬되어있어야 합니다. 이를 위해 STL의 Sort 함수를 이용합니다.
◆ 코드
#include <iostream>
#include <stdio.h>
#include<vector>
#include<algorithm>using namespace std;
int bar_search(vector<int> sang, vector<int> arr, int begin, int end, int key) {
int mid;while (begin<=end) {
mid = (begin + end) / 2;
if (key == sang.at(mid)) { // SANG의 절반에 해당하는 mid와 arr의 해당 수를 같은지 비교
return 1; // 맞으면 1반환
}
else if (key > sang.at(mid)) {
begin = mid + 1;
}
else {
end = mid - 1;
}
}
return -1;
}int main(){
int num_a,num_b,temp;
cin >> num_a;
vector<int> sang;for (int i=0; i < num_a; i++) { // 상근이가 가진 카드 입력
cin >> temp;
sang.push_back(temp);
}cin >> num_b;
vector<int> arr;
vector<int> arr_chk;for (int i = 0; i < num_b; i++) { // 배열 입력받음, 체크배열 0으로 초기화
cin >> temp;
arr.push_back(temp);
arr_chk.push_back(0);
}
// 비교하기 이전, 이진탐색을 위해 상근이가 가진 카드 정렬
sort(sang.begin(), sang.end());for (int i = 0; i < arr.size(); i++) {
temp = bar_search(sang,arr , 0, sang.size(), arr.at(i));
if (temp == -1) {
}
else {
arr_chk[i] = 1;
}
}
for (int i = 0; i < arr_chk.size(); i++) { // 결과값 출력
cout << arr_chk[i] << " ";
}return 0;
}
by. 구 본철