[BOJ] 1746 듣보잡

1764번: 듣보잡

문제

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.

듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

출력

듣보잡의 수와 그 명단을 사전순으로 출력한다.

---

풀만한 백준 문제를 찾던 도중에 code.plus라고 문제가 난이도 별로 정리되어 있는 걸 발견했다. 그중 자료구조 2에서 고른 문제이다. 알고리즘 분류가 '해쉬를 사용한 집합과 맵'으로 되어있었다. 난이도는 실버 4였지만 해쉬를 한 번도 사용해본 적이 없어서 이 문제를 골랐다.

 

일단 이 문제는 문자열 집합 두개를 주고 교집합을 찾는 문제였다. 첫 번째 문자열 집합을 해쉬 테이블로 만들어놓고, 두 번째 문자열 집합의 입력이 하나 들어올 때마다 그 문자열이 해쉬 테이블에 있는지 검사하면 될 것 같았다. 그래서 내가 알고 있는 만큼 해쉬를 러프하게 구현해봤다. 해쉬 함수는 간단하게 문자열의 첫 번째 문자가 몇 번째 알파벳인지로 사용했다. 입력 예시는 잘 출력됐지만 제출하면 시간 초과가 났다. 그래서 해쉬 함수를 좀 더 복잡하게(복잡해봤자긴 함) 만들어서 출력해봤는데도 여전히 시간 초과였다. 이렇게 계속해봤자 시간 낭비일 것 같아서 다른 사람의 풀이를 참고했다.

 

구글에 검색하니 많이 나오지도 않았다. 하나 정도 나왔던 것 같은데, 그 풀이는 해쉬를 사용하지 않고 C++ STL의 set을 사용하고 있었다. 찾아보니 set은 내부적으로 균형 이진 트리에 오름차순으로 정렬도 되어있었다. 이진트리면 원소가 삽입될 때 중복 찾기도 편할 것 같았다. 대충 O(logn) 정도의 성능일 것이고 그 정도면 시간 초과로부터 안전할 것 같긴 했다. 그런데 뭔가 완전 빡 해쉬를 기대했는데 별로 맛이 없었다.  

 

후기)

해쉬 자료구조를 조금 더 연습해보자. 삼성 특강 다음주엔 해쉬 공부하는 것 같긴하던데 어떤 맛일지 기대된다.