[C++,구현] 백준 1764번 듣보잡 문제풀이, 배열,vector,map 속도비교

문제링크

백준 1764번 듣보잡 

1764번: 듣보잡

 

간단한 문제열 처리문제를 가지고 흔히 알고리즘에서 사용하는 단순 배열, STL vector, STL map을 써서 

다양한 방법으로 문제를 풀어보고 속도차이를 비교해보려 한다.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n,m,cnt=0;
string nhs[1000000];
 
main(){
    cin>>n>>m;
    for(int i=0;i<n+m;i++)
        cin>>nhs[i];
        
    std::sort(nhs,nhs+n+m);
    for(int i=1;i<n+m;i++)
        if(nhs[i]==nhs[i-1])
                cnt++;    
    cout<<cnt<<'\n';
            
    for(int i=1;i<n+m;i++)
        if(nhs[i]==nhs[i-1])
            cout<<nhs[i]<<'\n';
    
}

메모리 37864kb

수행시간 132ms

위와 같은 최악(?)의 결과를 낳은 최초코드부터 리뷰를 하자면.. 우선 ios::sync_with_stdio(0); 를 안쓰고 cin을 써버리니 

수행시간이 최악으로 나와버렸다..ㅜ string배열을 최대치까지 할당해 메모리도 많이 들었다.

스트링 배열에 입력 문자열을 모두 받고 sort를 진행한 후 2개 이상의 문자열이 중복되어 있으면 출력하는 단순한 알고리즘을 사용하였다.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n,m,cnt=0;
string nhs[1000000];
 
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cin>>n>>m;
    for(int i=0;i<n+m;i++)
        cin>>nhs[i];
        
    std::sort(nhs,nhs+n+m);
    for(int i=1;i<n+m;i++)
        if(nhs[i]==nhs[i-1])
                cnt++;    
    cout<<cnt<<'\n';
            
    for(int i=1;i<n+m;i++)
        if(nhs[i]==nhs[i-1])
            cout<<nhs[i]<<'\n';
    
}

메모리 37864kb

수행시간 64ms

다음은 ios::sync_with_stdio(0);코드를 추가한 수행시간과 매모리이다.. 역시 갓 sync...

알고리즘은 전코드와 똑같다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int n,m,cnt=0;
vector <string> nhs;
 
main(){
    ios::sync_with_stdio(0);
 
    cin>>n>>m;
    nhs.resize(n+m);
    for(int i=0;i<n+m;i++)cin>>nhs[i];
        
    sort(nhs.begin(),nhs.end());
    for(int i=1;i<n+m;i++)
        if(nhs[i]==nhs[i-1])
                cnt++;    
    cout<<cnt<<'\n';
            
    for(int i=1;i<n+m;i++)
        if(nhs[i]==nhs[i-1])
            cout<<nhs[i]<<'\n';
    
}

메모리 9876kb

수행시간 48ms

이번에는 배열 대신 스트링 벡터를 사용하였다. 알고리즘은 똑같고 단순 배열만 벡터로 바꿨을 뿐인데 

수행시간과 메모리가 획기적으로 준것을 확인하였다. 벡터.. 자주사용하자!

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
 
using namespace std;
int n,m,cnt=0;
vector <string> ns,ans;
 
main(){
    ios::sync_with_stdio(0);
 
    cin>>n>>m;
    ns.resize(n);
    for(int i=0;i<n;i++)cin>>ns[i];
    
    sort(ns.begin(),ns.end());
    
    for(int i=0;i<m;i++){
        string k;
        cin>>k;
        if(binary_search(ns.begin(),ns.end(),k))ans.push_back(k);
    }
    cout<<ans.size()<<'\n';
    sort(ans.begin(),ans.end());
    for(vector<string>::iterator it=ans.begin();it!=ans.end();it++) cout<<*it<<'\n';
    
}

메모리 5936kb

수행시간 32ms

이번코드는 이문제에서 가장 좋은 성능을 나타낸 코드이다. 벡터를 사용하였고 입력을 받을 때 algorithm 헤더에 들어있는

 binary_search 알고리즘을 사용하였다. 찾은 string을 다시 벡터에 넣고 정렬한 후 iterator로 다시 출력한 코드이다.

#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
 
int n,m,cnt=0;
string s;
 
main(){
    scanf("%d%d",&n,&m);
    
    map<string, int> mp;
    
    for(int i=0;i<n;i++){
        cin>>s;
        mp[s]=1;
    }
    
    for(int i=0;i<m;i++){
        cin>>s;
        if(mp.find(s)!=mp.end()){
            cnt++;mp[s]++;
        }
    }
    
    printf("%d\n",cnt);
    map<string,int>::iterator it =mp.begin();
    while(it!=mp.end()){
        if(it->second==2)cout<<it->first<<'\n';
        it++;
    }
    
}

메모리 7408kb

수행시간 108ms

 STL map을 사용한 코드이다. map에 string을 넣어주고  다시 2번째 입력을 받을 때 map의 find함수를 이용해 안에 있는 string이 나오면 value값을 증가시켜 결국 마지막엔 value가 2인 string(key) 값만 출력하는 방법을 사용하였다.

 

여러 STL을 사용해보니 vector가 시간상으로 가장 효율적이고 map도 STL 사용법만 알아두면 유용하게 쓰인 것이란 생각이 들었다. map, count(), erase(), find()!!