문제 링크

문제

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

입력

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

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

출력

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

문제가 묘하게 성의 없는 것 같은 느낌?!

접근 과정

  1. 질문 게시판에서 질문자가 자바로 풀고 있었길래 본인도 자바를 사용하여 풀었다.
  2. 두 개의 그룹이 있고 각 그룹에 공통된 요소가 있는지 찾는 문제였다. 이 때 듣지 못한 그룹과 보지 못한 그룹의 크기가 최대 \(5 \times 10^{5}\)이므로 하나하나 비교하기 위해선 \(2.5 \times 10^{11}\)회의 연산이 필요하다. 이는 2초의 제한시간으론 부족해보였다.
  3. 따라서 O(n)보다 빠르게 요소를 탐색할 필요가 있었다. 풀고 다른사람들의 풀이를 봤을 떄 이분 탐색을 사용하였는데 본인은 O(1)의 속도로 요소가 있는지 확인할 수 있는 HashSet 클래스를 사용해봤다. 듣지 못한 그룹을 HashSet에 저장하고 보지 못한 그룹을 입력받을 때 HashSet에 동일한 이름이 있는지 찾도록 구현하였다.
  4. 처음에는 결과를 ArrayList에 저장하였으나 문제에 결과를 사전순으로 출력해야 한다는 조건을 고려하지 않아 틀리고 말았다. 예제 입력은 사전순으로 주었으나 테스트케이스에선 아니었던 모양. Collections 클래스의 sort 메소드를 사용하거나 자동으로 정렬되는 TreeSet 클래스를 사용하여 해결할 수 있는데 본인은 TreeSet을 사용하였다. 두 방법 중 어떤게 더 속도가 빠를진 솔직히 잘 모르겠다.

C++ STL에도 동일한 동작의 자료구조 클래스들이 존재한다.

  • HashSet -> std::unordered_map
  • TreeSet -> std::map

소스 코드

import java.util.HashSet;
import java.util.Scanner;
import java.util.TreeSet;

public class BOJ_1764 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        HashSet<String> cantHear = new HashSet<>();
        TreeSet<String> cantHearAndSee = new TreeSet<>();
        int N, M;

        N = sc.nextInt();
        M = sc.nextInt();

        for (int i = 0; i < N; ++i) {
            String name = sc.next();
            cantHear.add(name);
        }

        for (int i = 0; i < M; ++i) {
            String name = sc.next();
            if (cantHear.contains(name)) {
                cantHearAndSee.add(name);
            }
        }

        System.out.println(cantHearAndSee.size());
        for (String name : cantHearAndSee) {
            System.out.println(name);
        }

        sc.close();
    }
}