[BOJ] 21774

가희의 로그

N개의 로그 Q개의 임무
시작시간 - 종료시간
로그 레벨 lv 이상인 로그가 몇번 발생했는지
시작시각과 종료시간에 발생한 로그 포함

---

생각

문자열로 그대로 비교해보기

입력 받은 대로 파싱 진행 - : # 제거해서 문자열로 저장

처음에는

• 1 ≤ N ≤ 2×105
• 1 ≤ Q ≤ 2×105

이 조건을 생각하지 않고 마지막에 for문을 사용해 비교했다가 시간초과가 계속 생겼다.

이분 탐색을 사용한 후에도 시간초과가 나길래 혹시 몰라

ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 를 추가해보니 바로 해결됐다.

다음 부턴 그냥 기본으로 ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);를 박고 코드를 짜야겠다

---

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, q;
    cin>> n >> q;
    vector<string> log[7];

    // 로그
    for(int i=0; i<n; i++){
        string date, timelv, tmp="";
        cin >> date >> timelv;
        for(int j=0 ; j< date.size(); j++){
            if(date[j] != '-'){
                tmp += date[j];
            }
        }
        for(int j=0 ; j< timelv.size()-2; j++){
            if(timelv[j] != ':'){
                tmp += timelv[j];
            }
        }
        int lv = timelv[timelv.size()-1] -'0';
        for(int k=1;k<=lv;k++)log[k].push_back(tmp);
    }

    // Query
    
    for(int i=0 ;i<q; i++){
        string startQuery, endQuery;
        string first, mid, last, s1="",s2="";
        int ans=0;
        int lvcheck;
        cin >> first >> mid >> last;
        for(int j=0 ; j< first.size(); j++){
            if(first[j] != '-'){
                s1 += first[j];
            }
        }
        for(int j=0 ; j< mid.size(); j++){
            if(mid[j] != ':' && j < 8){
                s1 += mid[j];
            }
            else if(mid[j] != '-' && j>8){
                s2 += mid[j];
            }
        }
        for(int j=0 ; j< last.size()-2; j++){
            if(last[j] != ':'){
                s2 += last[j];
            }
        }
        startQuery = s1;
        endQuery = s2;
        lvcheck = last[last.size()-1] -'0';
    
        int upperbound = upper_bound(log[lvcheck].begin(), log[lvcheck].end(), endQuery) - log[lvcheck].begin();
        int lowerbound = lower_bound(log[lvcheck].begin(), log[lvcheck].end(), startQuery) - log[lvcheck].begin();
        ans = upperbound - lowerbound;
        cout << ans << '\n';
    }

}

가희의 로그

N개의 로그 Q개의 임무
시작시간 - 종료시간
로그 레벨 lv 이상인 로그가 몇번 발생했는지
시작시각과 종료시간에 발생한 로그 포함