[백준/C++] 1764번: 듣보잡 - set_intersection과 inserter 활용하기

1. 문제 정보

• 문제 번호: 1764번
• 문제 이름: 듣보잡
• 문제 요약: 듣도 못한 사람의 명단과 보도 못한 사람의 명단이 주어질 때, 두 명단에 모두 포함된 사람(듣보잡)의 수와 명단을 사전순으로 출력하는 문제이다.
  
  
  

2. 접근 방법 (알고리즘)

처음 문제를 읽자마자 두 집합의 교집합을 구하는 문제임을 파악했다. 명단의 크기가 각각 최대 500,000이므로 효율적인 탐색과 정렬이 필수적이다.

1. 자료구조 선택: std::set은 데이터를 삽입함과 동시에 자동으로 정렬하며, 중복을 허용하지 않는다. 또한 탐색 속도가 O(log N)으로 빨라 대규모 데이터를 다루기에 적합하다.
2. 교집합 연산: 두 집합에서 공통 원소를 찾기 위해 알고리즘 헤더(<algorithm>)의 set_intersection 함수를 사용하기로 했다. 이 함수는 정렬된 두 범위를 비교하여 공통 원소를 찾아낸다.
3. 결과 저장: 교집합의 결과를 새로운 집합에 담기 위해 출력 반복자(Output Iterator)인 std::inserter를 활용했다.

 

 

3. 코드 구현 (정답)

#include <iostream>
#include <set>
#include <algorithm> // set_intersection 사용을 위함

using namespace std;

int main() {
    // 입출력 최적화
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    string name;
    cin >> n >> m;

    set<string> A, B, C;

    // 1. 듣도 못한 사람 입력
    for(int i = 0; i < n; i++){
        cin >> name;
        A.insert(name);
    }

    // 2. 보도 못한 사람 입력
    for(int i = 0; i < m; i++){
        cin >> name;
        B.insert(name);
    }

    // 3. 두 집합의 교집합 구하기
    // inserter는 결과를 집합 C에 insert 연산으로 넣어주는 역할
    set_intersection(A.begin(), A.end(), 
                     B.begin(), B.end(), 
                     inserter(C, C.begin()));

    // 4. 결과 출력 (set이므로 이미 사전순 정렬됨)
    cout << C.size() << "\n";
    for(auto s : C){
        cout << s << "\n";
    }

    return 0;
}

---

4. 배운 점 & 회고 (TIL) ✍️

문제를 해결하면서 C++ 표준 라이브러리가 제공하는 강력한 집합 연산 기능과 반복자의 개념을 다시 한번 정리할 수 있었다.

① std::set_intersection 함수

이 함수는 두 개의 정렬된 범위를 받아 공통된 원소를 찾아낸다.

• 주의점: 비교 대상이 되는 두 컨테이너가 반드시 정렬된 상태여야 한다. set은 항상 정렬되어 있으므로 이 함수를 쓰기에 최적의 자료구조이다.
• 시간 복잡도: 두 집합의 크기가 N, M일 때 O(N + M)으로 매우 효율적이다.

② std::inserter와 출력 반복자

set_intersection의 다섯 번째 인자에는 결과가 저장될 위치를 지정하는 출력 반복자가 들어간다.

• 문제점: 일반적인 반복자(iterator)를 넣으면 결과를 덮어쓰려 하므로 공간이 부족할 경우 에러가 발생한다.
  ( 일반 반복자는 '기존 공간'을 가리키며 값을 덮어쓴다. 출력(삽입) 반복자는 값을 대입할 때 컨테이너의 삽입 함수를 호출하여 새로운 공간을 만든다)
• 해결책: inserter(container, position)를 사용하면, 내부적으로 container.insert()를 호출하여 새로운 원소를 추가해 준다.
• 깨달음: C++은 반복자(Iterator)라는 추상화 레이어를 정말 잘 활용하는 언어라는 점을 느꼈다. 특정 알고리즘 함수가 컨테이너의 내부 구현을 몰라도 반복자를 통해 데이터를 넣거나 뺄 수 있다는 점이 인상적이다.

③ 자료구조와 함수의 조화

만약 vector를 썼다면 데이터를 다 받은 뒤 따로 sort를 해야 했겠지만, set을 사용함으로써 입력과 동시에 정렬 문제를 해결했고, 교집합 연산 결과 역시 자동으로 정렬된 상태로 얻을 수 있었다. 문제의 조건(사전순 출력)을 고려할 때 가장 깔끔한 선택이었다고 생각한다.