10815번

10815번 - 숫자 카드

이분 탐색을 통해서 풀 수 있었다.

우선 가지고 있는 카드들은 sort() 함수를 통해서 오름 차순으로 정렬한다.

(이분 탐색은 정렬되어져 있는 데이터 중에서 원하는 값을 찾을 때 중요하다는 것을 깨달았다. 이전 이분탐색에서는 그냥 완전탐색을 좀 빠르게 한다라고

생각한다고 써놨었다. 그런데 질문도 올리고 그러면서 다른분의 말씀을 들으니 정렬되어있다! 라는게 정말 중요한 말이었다.

이전 문제들도 따로 정렬은 안했지만 찾고자 하는 값이 0 ~ 랜선의 길이, 나무의 최대 높이 처럼 정렬되어 있는 값이었던 것이었다.)

그 뒤 이번 문제는 배열의 인덱스를 가지고 , lo 와 hi 를 변화시켜주면서 가장 가까운 인덱스 값을 찾는다. 

그 가장 가까운 값이 내가 찾고 있는 값이라면 1을, 그렇지 않다면 0을 출력하면 된다.

@문제점

이분 탐색을 풀다보니 , 문제에서 요구하는 것을 생각하지 않고 풀어 처음에는 인덱스로 접근하지 못하고, 값 자체로 접근을 하였다.

하지마 값 자체로 접근을 하면 무조건 1을 출력하게 된다. 상근이가 가지고 있지 않은 값을 찾아진다는 것을 놓쳤기 때문이었다.

<정답 코드>

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int main()
{
    int N, M;
    vector<int> have;
    vector<int> toCompare;
    vector<int> answer;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int tmp;
        cin >> tmp;
        have.push_back(tmp);
    }
    cin >> M;
    for (int j = 0; j < M; j++)
    {
        int tmp;
        cin >> tmp;
        toCompare.push_back(tmp);
    }
 
    sort(have.begin(), have.end());
 
    for (int i = 0; i < toCompare.size() ; i++)
    {
        int lo = 0;
        int hi = have.size();
        int mid;
 
        for (int it = 0; it < 100; it++)
        {
            mid = (lo + hi) / 2;
 
            if (have[mid] < toCompare[i])
            {
                lo = mid;
            }
            else if(have[mid] > toCompare[i])
            {
                hi = mid;
            }
            else if (have[mid] == toCompare[i])
            {
                lo = mid;
                break;
            }
 
        }
 
        if (have[lo] == toCompare[i])
        {
            cout << "1 ";
        }
        else
        {
            cout << "0 ";
        }
    
    }
 
    return 0;
}