백준 11116 교통량

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

11116번: 교통량

문제 해설

왼쪽 줄을 지나간 시간과

오른쪽 줄을 지나간 시간이 주어질 때,

왼쪽에서 오른쪽으로 지나간 교통량을 구하는 문제다.

 

왼쪽에서 오른쪽으로 지나간 교통량이 될 수 있는 경우는

왼쪽 줄에 t, t+500이, 오른쪽 줄에 t+1000, t+1500이 존재하는 t이다.

map을 이용해 각각 log(n) 시간에 탐색해 해결할 수 있다.

 

#include <iostream>
#define fio cin.tie(0)->sync_with_stdio(0)
using namespace std;

#include <set>
int main(){
    fio;
    int T; cin >> T;
    for(int t = 1; t <= T; t++){
        //
        int N; cin >> N;
        set<int> left, right;
        for(int i=0; i < N; i++){
            int tmp; cin >> tmp;
            left.insert(tmp);
        }
        for(int i=0; i < N; i++){
            int tmp; cin >> tmp;
            right.insert(tmp);
        }
        int cnt = 0;
        set<int>::iterator iter;
        for(iter = left.begin(); iter != left.end(); iter++){
            int now = *iter;
            if(left.find(now+500) != left.end() &&
                right.find(now+1000) != right.end() &&
                    right.find(now+1500) != right.end()){
                        cnt++;
                    }
        }
        cout << cnt <<'\n';
        //
    }

    return 0;
}