[JAVA] 백준 (실버4) 1764번 듣보잡

링크

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

---

문제 설명

정답률 41.480%

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

---

입력 예제

3 4
ohhenrie
charlie
baesangwook
obama
baesangwook
ohhenrie
clinton

---

출력 예제

2
baesangwook
ohhenrie

---

풀이

듣도 못한 사람과 보도 못한 사람의 교집합을 구해야 한다. 단순히 모든 원소에 대해 1대1 비교를 하면 시간초과가 발생한다. 따라서 우선 듣도 못한 사람을 기준으로 보도 못한 사람이 포함됐는지 여부에 따라 새로운 집합을 만든다.

이때 HashSet의 contains 메서드를 이용한다. HashSet은 해시 함수를 이용해 요소를 저장하고 관리한다. 요소를 검색할 때 해시 값을 통해 바로 접근할 수 있기 때문에 평균적으로 $O(1)$의 시간 복잡도를 가진다.

하지만 List를 사용할 경우는 시간 초과가 발생하는데 List는 순차적으로 요소를 저장하는 자료구조이기 때문이다. 따라서 contains 메서드는 리스트의 처음부터 끝까지 순차적으로 요소를 비교하여 찾고자 하는 요소가 있는지 확인한다. 최악의 경우, 찾고자 하는 요소가 리스트의 마지막에 있거나 리스트에 없는 경우 리스트의 모든 요소를 확인해야 하므로 $O(n)$의 시간 복잡도를 가진다.

전체 코드

//백준
public class Main {

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[] split = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        int N = split[0];
        int M = split[1];

        HashSet<String> set = new HashSet<>();
        List<String> result = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            set.add(br.readLine());
        }

        for (int i = 0; i < M; i++) {
            String name = br.readLine();
            if (set.contains(name)) {
                result.add(name);
            }
        }

        Collections.sort(result);
        System.out.println(result.size());
        result.forEach(System.out::println);
    }
}