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

문제

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

 

• 소요 시간 : 17분
• 난이도 : 실버 4

접근 방법

1) map 이용한 방법 

1. 이름-개수 를 저장한 map을 만든다.

2. 듣도못한사람, 보도못한사람을 입력받아 개수를 늘려준다.

3. 개수가 2인 것만 리스트를 만든다.

 

2) 정렬&포인터 이용한 방법

1. 듣도못한사람, 보도못한사람의 리스트를 만든다.

2. 각 리스트를 사전 순으로 정렬한다.

3. 각 리스트를 반복하는 인덱스를 만든다.

4. 2개의 인덱스를 비교하면서

이름이 같으면 듣도보도못한사람 리스트에 넣고, 

이름이 사전순으로 작으면 인덱스를 하나 올려 다음 것과 비교하도록 한다.

나의 풀이

1) map 이용한 방법 

- 메모리 : 12856 KB

- 시간 : 124ms

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

using namespace std;


map<string, int> m;
int N, M;

int main() {
    cin >> N >> M;

    // 듣도 못한 사람 
    string name;
    for(int i=0; i<N; i++) {
        cin >> name;
        m[name]++;

    }

    // 보도 못한 사람 
    for(int i=0; i<M; i++) {
        cin >> name; 
        m[name]++;
    }

    vector<string> answers;

    for(auto p : m) {
        if (p.second == 2)
            answers.push_back(p.first);
    }

    cout << answers.size() << "\n";

    for(string name : answers) {
        cout << name << "\n";
    }

    return 0;
}

 

2) 정렬&포인터 이용한 방법

- 메모리 : 9752KB

- 시간 : 104ms

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

using namespace std;


vector<string> listens, sees;
int N, M;

int main() {
    cin >> N >> M;

    // 듣도 못한 사람 
    string name;
    for(int i=0; i<N; i++) {
        cin >> name;
        listens.push_back(name);
    }

    // 보도 못한 사람 
    for(int i=0; i<M; i++) {
        cin >> name; 
        sees.push_back(name);
    }

    // 정렬
    sort(listens.begin(), listens.end());
    sort(sees.begin(), sees.end());

    int listensIdx = 0, seesIdx = 0;

    vector<string> listenSees;

    while(listensIdx < N && seesIdx < M) {

        string listenName = listens[listensIdx];
        string seeName = sees[seesIdx];

        if (listenName == seeName) {
            listenSees.push_back(listenName);
            listensIdx++;
            seesIdx++;
        } else if (listenName < seeName) {
            listensIdx++;
        } else {
            seesIdx++;
        }
    }

    cout << listenSees.size() << "\n";
    for(string name : listenSees) {
        cout << name << "\n";
    }
    
    return 0;
}

 

 

비교

1) map 이용한 방법 

• 메모리: map은 내부적으로 트리를 사용하여 데이터를 저장하기 때문에 메모리 사용량이 크다.
• 시간: map의 삽입 및 조회 연산이 평균적으로 O(log N)의 시간 복잡도를 가지므로, 입력 데이터 크기(N, M)에 대해 각각 O(N log N + M log M)의 시간이 소요된다. 
• 장점: 코드가 간결하고 직관적이다.
• 단점: 메모리 사용량이 높다.

2) 정렬&포인터 이용한 방법

• 메모리: 벡터 두 개를 사용하므로 메모리 사용량이 비교적 적다.
• 시간: 정렬에 O(N log N + M log M) 시간이 소요되고, 두 정렬된 벡터를 병합하는데 O(N + M)의 시간이 소요된다.
• 장점: 메모리 사용량이 적다.
• 단점: 코드가 약간 더 복잡하다.

결론

• 데이터의 크기가 매우 크고, 메모리 사용량이 중요한 경우 두 번째 방법을 사용하는 것이 좋겠다.
• 코드의 간결성과 유지 보수성을 생각한다면 첫 번째 방법도 고려할 수 있겠다.

 

정리

여러가지 방법으로 풀고 비교해보는 것도 재밌는 것 같다.