[이분탐색] 백준 1920 :: 수 찾기

수 찾기 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	33987	8981	5922	27.524%

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수들의 범위는 int 로 한다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제 입력 1 

5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1 

1
1
0
0
1

 

 문제 풀이

1차 풀이 (  2380 KB,  60 ms)

• 최대 100,000번 만큼 탐색을 요구하므로,
  정렬비용이 비싸더라도 오름차순으로 정렬한 뒤,
  여러번 이분탐색을 하는 것이 좋다.
• 데이터가 많으므로 stdio와 동기화를 해제한다.
  
• 기본적인 이분탐색이므로 자세한 해설은 이곳에서 하지 않는다.
  https://aerocode.net/237  이곳을 참고.
  

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
using int32 = int32_t;
using int64 = int64_t;


int32 N, A[100'000];
int32 M, MVal;

bool test(int32 idx){
        return A[idx] <= MVal;
}


int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);


        cin >> N;
        for(int32 i=0; i<N; i++) cin >> A[i];
        sort(A, A+N);

        cin >> M;
        int32 start, end, mid, ret;
        while(M--){
                cin >> MVal;
                start = 0; end = N; ret = 0;
                while(start < end){
                        mid = (start + end)/2;
                        if(test(mid)){
                                if(ret < mid) ret = mid;
                                start = mid+1;
                        }
                        else end = mid;
                }
                cout << (A[ret] == MVal) << '\n';
        }
}

2차 풀이 (  4428 KB,  28 ms)

• 저수준 입출력 사용.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <unistd.h>
using namespace std;
using int32 = int32_t;
using int64 = int64_t;

const int BUF_SIZE = 1 << 20;        // 메모리 초과 가능, 적당히 조절할 것.
char input_buf[BUF_SIZE], output_buf[BUF_SIZE];
int input_buf_pos, output_buf_pos;
enum io_mode {READ, WRITE};
inline void char_io(io_mode mode, char &target)
{
        if(mode == READ) {
                if (input_buf_pos == BUF_SIZE)
                {
                        fread(input_buf, sizeof(char), BUF_SIZE, stdin);
                        input_buf_pos = 0;
                }
                target = input_buf[input_buf_pos++];
        }
        else {
                if(output_buf_pos == BUF_SIZE || target == EOF)
                {
                        fwrite(output_buf, sizeof(char), output_buf_pos, stdout);
                        output_buf_pos = 0;
                }
                output_buf[output_buf_pos++] = target;
        }
}
inline void char_io(io_mode mode, char &&target){
        char_io(mode, target);
}

inline void int_io(io_mode mode, int &target)
{
        char c;
        if(mode == READ){
                bool negative = false;
                int ret = 0;
                while(true)
                {
                        char_io(READ, c);
                        if(c == '\n' || c == ' ') break;
                        if(c == '-') {
                                negative = true;
                                continue;
                        }
                        ret = ret * 10 + (c & 0b1111);
                }
                target = negative ? -ret : ret;
        }
        else {
                int abs = target;
                int div = 1'000'000'000;
                char quotient = 0;
                if(abs < 0) {
                        char_io(WRITE, '-');
                        abs *= -1;
                }
                while(abs < div && div != 1) { div /= 10; }
                while(div != 0){
                        quotient = '0' + (char)((abs / div)%10);
                        char_io(WRITE, quotient);
                        div /= 10;
                }
        }
}
inline void int_io(io_mode mode, int &&target){
        int_io(mode, target);
}

int32 N, A[100'000];
int32 M, MVal;

bool test(int32 idx){
        return A[idx] <= MVal;
}


int main() {
        int_io(READ, N);
        for(int32 i=0; i<N; i++) int_io(READ, A[i]);
        sort(A, A+N);

        int_io(READ, M);
        int32 start, end, mid, ret;
        while(M--){
                int_io(READ, MVal);
                start = 0; end = N; ret = 0;
                while(start < end){
                        mid = (start + end)/2;
                        if(test(mid)){
                                if(ret < mid) ret = mid;
                                start = mid+1;
                        }
                        else end = mid;
                }
                int_io(WRITE, A[ret] == MVal);
                char_io(WRITE, '\n');
        }
        char_io(WRITE, EOF);
}