[JAVA / 자바] 백준 1764번 - 듣보잡 (실버 4)
문제
김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+둘째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.
듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.
출력
듣보잡의 수와 그 명단을 사전 순으로 출력한다.
문제 접근 방법
이번 문제는 들도 못한 사람의 명단과 보도 못한 사람의 명단에 둘 다 포함되어 있는 듣도보도 못한 사람을 찾아 출력하는 문제이다. 그렇다면 문자열을 배열에 저장해 두고 해당 문자열의 저장 유무를 확인하는 문제가 되기 때문에 탐색이 빠른 자료구조를 사용하여야 한다. 따라서, 듣도못한 사람들의 명단을 HashSet을 사용하여 저장할 예정이다.
왜 HashSet에 저장해야 하는지 모르겠는 사람은 다음 포스팅을 참고하길 바란다. [JAVA / 자바] ArrayList vs HashSet
[JAVA / 자바] ArrayList vs HashSet
이번 포스팅은 ArrayList와 HashSet을 어떤 상황에 사용하면 좋을 지에 대해 말해보려 한다. 이전에 성능과 상관없이 코드를 작성할 때는 굳이 HashSet은 사용하지 않았다. 왜냐면 정렬도 되지 않고 순
kwin0825.tistory.com
듣도 못한 사람들의 명단을 HashSet에 저장했다면 다음 입력으로는 보도 못한 사람들이 등장할 차례이다. 물론 보도 못한 사람도 HashSet에 저장해 둘 순 있지만, 문제에서 원하는 출력은 듣도보도 못한 사람, 즉 두 그룹 모두에 포함된 사람만 출력하면 되는 것이다.
따라서 보도 못한 사람의 입력은 모두 저장해 둘 필요 없이 입력되는 대로 듣도 못한 사람들의 명단에 비교해보고 듣도 못한 사람들 명단에 포함되어있다면 듣도 보도 못한 사람들의 명단으로 저장해두면 된다.
그렇게 듣도보도 못한 사람들의 명단이 완성되었다면 출력은 사전 순으로 하라 했으므로 정렬을 한번 해주고 그 내용을 출력해주면 해결된다.
JAVA 코드 풀이
코드 실행 결과
후기
이번 문제는 HashSet에 대한 자료구조를 알고 있냐 모르느냐에 따라 문제의 정답처리가 달라지는 것 같다. HashSet에 대해 적당한 사용 시기를 알고 있다면 쉽게 해결되는 문제라 생각된다.
문제 원본
https://www.acmicpc.net/problem/1764
1764번: 듣보잡
첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다.
www.acmicpc.net