[BOJ] 백준 1764. 듣보잡

▶문제설명

[BOJ] 1764. 듣보잡

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

▶Hint

---

set을 이용하면 쉽게 풀 수 있는 문제이다. 해싱을 연습해볼 수 있는 문제이기도 하다.

STL의 set은 레드블랙트리로 구현되어 있다고 알려져있는데, 레드블랙트리는 삽입/삭제/검색에 O(logN)의 시간이 걸리는 자료구조이며, 중복을 허용하지 않는다는 특징이 있다.

듣도 못한 사람의 이름을 입력 받아 set에 저장해놓은 뒤, 보도 못한 사람의 이름을 입력받아 set에서 검색했을 때, 해당 이름이 존재하면 듣도 보도 못한 사람으로 분류한다.

듣도 보도 못한 사람들의 이름을 하나의 vector에 모두 저장하고, 사전 순으로 정렬시킨 뒤 출력하면 정답이 된다.

▶시간 복잡도

---

[제약 사항] 

N : 듣도 못한 사람의 수 

M : 보도 못한 사람의 수

L : 사람의 이름 길이

( 1 <= N, M <= 500,000 )

( 1 <= L <= 20 )

 

듣도 못한 사람 N 명을 저장하는 데 드는 시간 : O(L*N*logN)

보도 못한 사람 M 명을 검색하는 데 드는 시간 : O(L*logM)

듣도 보도 못한 사람 M명을 vector에 저장하고 정렬하는 데 드는 시간 : O(L*M*logM)

N이 더 크다고 가정했을 때,

전체적인 시간 복잡도 : O(2*N*logN + L*N*logN) = O(L*N*logN)

▶Solution