[BOJ] 22232 가희와 파일 탐색기

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

22232번: 가희와 파일 탐색기

쉬워 보이지만 시간이 많이 걸렸던 문제이다.

sort에 cmp함수에는 아무리 작은 계산이라도 넣으면 시간 초과가 난다는 것을 잊지 말자.

 

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

vector<pair<pair<string,string>,int > > all;
map<string,int> ex;

bool cmp(pair<pair<string,string>,int > a,pair<pair<string,string>,int > b){
    if(a.first.first==b.first.first){
        if(a.second==b.second) return a.first.second<b.first.second;
        return a.second<b.second;
    }
    return a.first.first<b.first.first;
}

int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
    int N,M;
    cin>>N>>M;
    for(int i=0;i<N;i++){
        string s;
        cin>>s;
        int idx = s.find('.');
        all.push_back(make_pair(make_pair(s.substr(0, idx),s.substr(idx + 1)),0));
    }
    for(int i=M;i>0;i--){
        string s;
        cin>>s;
        ex[s]=-1;
    }
    for(int i=0;i<N;i++){
        if(ex[all[i].first.second]==-1){
            all[i].second=-1;
        }
    }
    sort(all.begin(),all.end(),cmp);
    
    for(int i=0;i<N;i++){
        cout<<all[i].first.first<<"."<<all[i].first.second<<'\n';
    }
    
    return 0;
}