[C++][백준 1764] 듣보잡

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

제출 코드(시간 초과)

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

int main()
{
    int n, m, size;

    cin >> n;
    cin >> m;

    size = n + m;
    string* names = new string[size];

    vector<string> res;
    int idx = 0;

    for (int i = 0; i < n ; i++)
    {
        string name;
        cin >> names[i];
    }

    for (int i = 0; i < m; i++)
    {
        string compare;
        cin >> compare;
        for (int j = 0; j < n; j++)
        {
            if (names[j] == compare)
            {
                res.push_back(compare);
                idx++;
                break;
            }
        }
    }

    sort(res.begin(), res.end());

    cout << idx << endl;
    for (int i = 0; i < res.size(); i++)
    {
        if (res[i] == "") break;
        cout << res[i] << endl;
    }
}

N개 길이를 가진 배열을 동적으로 할당해서 뒤이어 나온 M개의 이름과 N개의 이름을 하나하나 비교하는 방식으로 코드를 작성했는데 시간 초과가 떴다

 

내가 구현한 방식은 시간복잡도가 큰 방식이라 시간 초과가 뜬 것 같다

 

반나절 넘게 고민해봐도 답이 떠오르질 않아 다른 사람들의 코드를 참고해보았다

 

1. map을 이용

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    map<string, int> names;
    vector<string> res;
    int n, m;

    cin >> n >> m;
    for (int i = 0; i < n + m; i++)
    {
        string name;
        cin >> name;
        
        names[name]++;
        if (names[name] > 1)
            res.push_back(name);
    }

    sort(res.begin(), res.end());

    cout << res.size() << '\n';
    for(auto n : res)
        cout << n << '\n';
}

map은 key와 value를 갖는 자료형이다

key값을 통해 value값을 찾아낼 수 있으며, 중복을 허용하지 않는다

내부의 검색, 삽입, 삭제는 시간복잡도가 O(logn)

기본적으로 오름차순으로 정렬하여 저장

* map 사용 시 헤더에 #include <map>을 명시해주어야 함

 

2. 이분탐색

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    vector<string> names, res;

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        string name;
        cin >> name;
        names.push_back(name);
    }

    sort(names.begin(), names.end());

    for (int i = 0; i < m; i++)
    {
        string name;
        cin >> name;
        if (binary_search(names.begin(), names.end(), name))
            res.push_back(name);
    }

    sort(res.begin(), res.end());

    cout << res.size() << '\n';
    for (auto r : res)
        cout << r << '\n';
}

binary_search() 함수(이분탐색)를 이용한 구현이다

정렬이 되어 있다는 가정 하에 이진 탐색을 통해 특정 값을 검색할 수 있다

* for(auto r : res) : res변수(vector, array 등)의 값을 차례로 r에 넣어서 반복하는 for문 (auto는 자료형을 자동으로 지정해준다는 뜻으로, 위 코드에서는 string으로 작성하여도 문제 없음)

 

아래는 map을 이용한 구현, 위는 이분 탐색을 이용한 구현

확실히 이분 탐색을 이용하는 방법이 더 빠름을 확인할 수 있다

 

참고: https://ongveloper.tistory.com/112