반응형 집합 자료구조1 [C/C++] 백준 #1764 듣보잡(집합자료) 이번 문제는 집합 자료를 사용하면 쉽게 풀리는 문제입니다. 문제는 들어본 적이 없는 사람들의 리스트와 본적 없는 사람들의 리스트가 주어졌을 때, 듣보잡(들어보지도, 본적도 없는) 리스트를 구하는 것입니다. 그런데, 최종 리스트는 사전순으로 배열해야 합니다. 가장 간단한 방법을 두 집합을 만들고, 그 집합의 교집합을 구하는 방법이겠죠. 정렬된 리스트를 만들고 교집합을 만들면 알고리즘 효율은 \(O(N \log N + M \log M)\)이 됩니다. 정렬하는데 필요한 부분입니다. 정렬한 두개의 리스트에서 교집합 내용을 찾는 것은 \(O(N+M)\)이 되겠죠. 저는 두개의 집합을 이용했습니다. 첫번째는 해시집합이고, 두번째는 정렬집합입니다. 해시집합은 정렬되지는 않았지만, 삽입, 검색이 모두 \(O(1)\)인.. 2022. 10. 15. 이전 1 다음 728x90
