[이분탐색] 백준 10816 :: 숫자카드 2

숫자 카드 2 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	9638	2832	1948	33.633%

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

예제 입력 1 

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

예제 출력 1 

3 0 0 1 2 0 0 2

     

 문제 풀이

1차 풀이 (  3940 KB,  348 ms)

• 해의 길이?
  배열을 정렬한 뒤, 이분탐색을 통해 lower_bound,  upper_bound를 탐색.
  해가 없는 경우가 있으므로,  val[lower_bound]가 정답인지 한번 더 체크.
  
  
• 데이터가 많다!
  입출력에서 부하가 걸릴 수 있으므로,
  stdio와의 동기화를 해제한다.

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

int32 N, M;
int32 val[500'000];
int32 valToFind;


bool lowerBoundTest(int32 idx){
        return valToFind <= val[idx];
}


bool upperBoundTest(int32 idx){
        return valToFind < val[idx];
}


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


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


        cin >> M;
        int32 srt, end, mid;
        int32 retSrt, retEnd;
        while(M--){
                retSrt = -1;
                retEnd =  N;
                cin >> valToFind;


                //! check upper_bound
                srt = 0;
                end = N;
                while(srt < end){
                        mid = (srt + end) / 2;
                        if(upperBoundTest(mid)){
                                retEnd = mid;
                                end = mid;
                        }
                        else srt = mid+1;
                }


                //! check lower_bound
                srt = 0;
                end = N;
                while(srt < end){
                        mid = (srt + end) / 2;
                        if(lowerBoundTest(mid)){
                                retSrt = mid;
                                end = mid;
                        }
                        else srt = mid+1;
                }


                //! check valid;
                if(val[retSrt] != valToFind) cout << 0;
                else cout << (retEnd - retSrt);
                cout << ' ';
        }
}

2차 풀이 (  5988 KB,  200 ms)

• 데이터가 너무 많다!
  버퍼를 사용한, 저수준 입출력 사용.

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

#include <iostream>
#include <cstring>
using namespace std;
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, M;
int32 val[500'000];
int32 valToFind;


bool lowerBoundTest(int32 idx){
        return valToFind <= val[idx];
}


bool upperBoundTest(int32 idx){
        return valToFind < val[idx];
}


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


        int_io(READ, N);
        for(int32 i=0; i<N; i++) int_io(READ, val[i]);
        sort(val, val+N);


        int_io(READ, M);
        int32 srt, end, mid;
        int32 retSrt, retEnd;
        while(M--){
                retSrt = -1;
                retEnd =  N;
                int_io(READ, valToFind);


                //! check upper_bound
                srt = 0;
                end = N;
                while(srt < end){
                        mid = (srt + end) / 2;
                        if(upperBoundTest(mid)){
                                retEnd = mid;
                                end = mid;
                        }
                        else srt = mid+1;
                }


                //! check lower_bound
                srt = 0;
                end = N;
                while(srt < end){
                        mid = (srt + end) / 2;
                        if(lowerBoundTest(mid)){
                                retSrt = mid;
                                end = mid;
                        }
                        else srt = mid+1;
                }


                //! check valid;
                if(val[retSrt] != valToFind) int_io(WRITE, 0);
                else int_io(WRITE, retEnd - retSrt);
                char_io(WRITE, ' ');
        }
        char_io(WRITE, EOF);
}