[백준 1764번] 듣보잡

1764번: 듣보잡 (acmicpc.net)

 

문제를 읽으면 쉬워보이는 데, 시간 제한이 걸려 있어서 생각을 더 해봐야했던 문제 

정말 단순하게 생각하면, 이중 for문을 사용해서 풀 수 있다.

근데 복잡도가 O(n^2)이라 그렇게 제출하면 시간초과가 떠버리는ㅠ

그렇게 제출한 잘못된 코드는

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    int n, m;
    int count = 0;
    cin >> n >> m;
    
    vector<string> d, b, db;
    string name;
    for(int i=0; i<n; i++){
        cin >> name;
        d.push_back(name);
    }
    
    for(int i=0; i<m; i++){
        cin >> name;
        b.push_back(name);
    }
    
    sort(d.begin(), d.end());
    sort(b.begin(), b.end());
    
    for(int i=0; i<d.size(); i++){
        for(int j=0; j<b.size(); j++){
            if(d[i] == b[j]){
                count++;
                db.push_back(d[i]);
                break;
            } 
        }
    }
    
    cout << count << endl;
    for(int i=0; i<db.size(); i++){
        cout<<db[i] << endl;
    }
   
    return 0;
}

정렬을 이용하고, 찾으면 break를 하는 방법을 통해 시간이 조금 단축될까 했는데

그래봤자 시간복잡도는 O(n^2)이라 안됨

 

벡터를 2개를 사용하면 이중 for문이 나올 수 밖에 없는 구조라 해야했던 방법은 배열을 1개로 줄이는 것

되도 않는 놈과 보도 못한 놈을 한 배열에 input을 받고 sorting하면

듣보잡은 한배열에 이름이 2개씩 존재할테니

그걸 이용하면 됨

 

내 아이디어는 아니고 교수님 풀이인데.... 이마 탁탁 치면서 들었던

그렇게 나온 코드는 이러함

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    int n, m;
    int count = 0;
    cin >> n >> m;
    
    vector<string> d, result;
    string input;
    for(int i=0; i<n+m; i++){
        cin >> input;
        d.push_back(input);
    }

    sort(d.begin(), d.end());
   
   for(int i=0; i<d.size(); i++){
        if(d[i] == d[i+1]) {
            count++;
            result.push_back(d[i]);
        }
        
    }
    cout << count << endl;
    for(int i=0; i<result.size(); i++) cout<<result[i] << endl;
    
    return 0;
}