백준 10815 - 숫자 카드

1. 문제 정리
  - N개의 수와 M개의 수가 주어진다.

  - M개의 수 각각이 N개의 수 배열에 포함되는지를 검증한다.
 
2. 접근
  - 전형적인 이진탐색 문제라고 생각했다.

  - N개의 수가 들어있는 배열은 정렬을 하고, M개의 수는 그대로 사용하고자 하였다.

  - M개의 수를 N개의 배열에 이진탐색을 시도하는 것으로 시간 복잡도는 O(M*logN)이며, 이는 최대값으로 보았을 때, 500000*log(500000) = 약 1100만 이므로 2초 시간제한 안에 들어온다.
 
3. 풀이

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

int n, m;
vector<int> a;
vector<int> comp;

bool bis(int target){
    int hi, lo;
    hi = n-1;
    lo = 0;
    while(lo <= hi){
        int mid = (lo+hi) / 2;
        if(target == a[mid]) return true;
        if(target < a[mid]) hi = mid-1;
        else lo = mid+1;
    }
    return false;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n;
    for(int i = 0; i < n; i++){
        int input;
        cin >> input;
        a.push_back(input);
    }
    sort(a.begin(), a.end());
    cin >> m;
    for(int i = 0; i < m; i++){
        int input;
        cin >> input;
        comp.push_back(input);
    }

    for(int i = 0; i < m; i++){
        if(bis(comp[i]))cout << 1 << ' ';
        else cout << 0 << ' ';
    }
}

  - vector<int> a, vector<int> comp : a는 N개의 정수, comp는 M개의 정수를 저장할 벡터이다.

  - bool bis(int target) : target값이 a 벡터에 존재하는 지 이진탐색으로 결과를 반환하는 함수이다.

  - int main() : 마지막 for loop에서 bis를 각 comp 벡터의 원소 값을 target parameter로 전달하여 실행하고 그 결과에 따라 반환값이 true일 경우 1, false일 경우 0을 출력한다.
 
4. 소감

  그다지 어렵지는 않은 문제였지만, 이진탐색 문제를 풀어보기 시작한 나에게는 적당한 문제였던 것 같다. 긴장감도 낮춰주고 조금씩 적응해나갈 수 있게 해준 문제라 좋았다. 시간 복잡도 계산도 최근 들어 더 열심히 하려고 노력 중이라, 문제를 보고 겁먹기 보다는 생각난 아이디어를 논리적으로 분석해서 가능성이 있을지를 판단하는 것을 더 노력해야겠다고 생각했다.