[백준 알고리즘] 1764번 : 듣보잡

문제

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

입력

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

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

출력

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

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_1764 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        HashSet<String> hs = new HashSet<>();
        LinkedList<String> result = new LinkedList<>();

        //HashSet에 듣도 못한 사람의 명단 저장
        for (int i = 0; i < N; i++) hs.add(br.readLine());

        for (int i = 0; i < M; i++) {
            String s = br.readLine();
            if (hs.contains(s)) result.add(s);
        }
        Collections.sort(result);

        System.out.println(result.size());
        for (String i : result) System.out.println(i);
    }
}

풀이 및 느낀점

• 풀이 방법
  HashSet을 사용했다.
  먼저 듣도 못한 사람의 명단을 HashSet에 저장했다. 보도 못한 사람의 명단을 입력받은 후, 이름이 HashSet(듣도 못한 사람의 명단)에 존재한다면 LinkedList에 보도 못한 사람의 이름을 추가한다.
  듣도 보도 못한 사람의 이름을 LinkedList에 모두 저장한 후, 오름차순으로 정렬하여 출력해준다.

• HashSet이란?
  HashSet은 Set 인터페이스의 구현 클래스이다. 따라서 Set의 성질을 그대로 상속받는다. Set은 객체를 중복해서 저장할 수 없고 하나의 null 값만 저장할 수 있다. 또한 저장 순서가 유지되지 않는다. Set의 가장 큰 장점은 중복을 자동 제거해준다는 점이다. Set은 비선형 구조이기 때문에 순서가 없고 인덱스 또한 존재하지 않는다. 따라서 값을 추가하거나 삭제하고자 하는 값이 Set 내부에 있는지 검색한 뒤 추가나 삭제를 해야 하므로 속도가 List 구조에 비해 느리다.

• HashSet과 ArrayList의 시간복잡도
  HashSet의 contains() -> O(1)
  ArrayList의 contains() -> O(n)
  HashSet은 map 기반으로 구현되고, ArrayList는 indexOf()를 사용해서 contain 여부를 결정한다. 효율성이 필요한 문제는 HashSet을 사용하자.

참고자료