백준 1920 (수 찾기)

https://www.acmicpc.net/problem/1920

숼명

일단, 메모리 복잡도로 인해 배열에 담아서 셀 수 없고, 시간 복잡도로 인해 O(N^2)는 또 넘으면 안된다.
방법이 없다고 생각했는데 퀵정렬을 사용하면 된다는 힌트를 보고 풀었다. 총 복잡도는 O(NlgN)이다.
다음부터 복잡도 못 줄이겠는데...싶은건 그냥 무작정 정렬하지는 않지만 정렬 방법들이 적용된다고 가정하고 풀어봐야 겠다.

사실 퀵 정렬보다 골 아팠던 부분이 while문의 범위조건이었다. 처음 또는 마지막에 답이 있을 때, 그리고 아예 찾고자 하는 수가 배열에 존재하지 않을 때의 범위를 생각해 내는 것이 힘들었다. 나는 항상 범위 설정을 정말 못 한다ㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎ하

cod turned in

#include <bits/stdc++.h>
using namespace std;
int n, m;
int input[100001];
int here[100001];

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(0);

    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> input[i];
    cin >> m;
    for (int i = 0; i < m; i++)
        cin >> here[i];
    
    sort(input, input + n);
    
    for (int i = 0; i < m; i++)
    {
        int st = 0;
        int flag = 0;
        int en = n;
        while (en - st != 0)
        {
            int mid = (en + st) / 2;
            if (here[i] < input[mid])
                en = mid;
            else if (here[i] > input[mid])
                st = mid + 1;
            else
            {
                cout << "1\n";
                flag++;
                break;
            }
        }
        if (!flag)
            cout << "0\n";
    }
    return (0);
}