문제 출처

단계별로 풀어보기 > 집합과 맵 > 듣보잡
https://www.acmicpc.net/problem/1764

문제 설명

듣도 못한 사람 N, 보도 못한 사람 M이 주어질 때, 듣도 보도 못한 사람의 수와 각각 사람의 이름을 출력하라.

접근 방법

HashSet을 이용하여 풀이한다. 듣도 못한 사람 N명을 HashSet에 저장하고, 보도 못한 사람 M명을 contains 메서드를 통해서 확인한다. 만약 HashSet안에 있다면, result에 저장한다.
저장된 내용을 사전순으로 정렬하고, 순차적으로 StringBuilder에 추가한다.

import java.io.*;
import java.util.*;

public class 듣보잡 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

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

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

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

        StringBuilder sb = new StringBuilder();

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

        for(int j = 0; j < M; j++){
            String str = br.readLine();
            if(hs.contains(str)){
                result.add(str);
            }
        }

        Collections.sort(result);
        sb.append(result.size()).append("\n");

        for(String s : result){
            sb.append(s).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

해당 풀이의 시간 복잡도는 O(N + M + klogk)의 값을 가진다. 기본적으로 N개를 처리하는 반복문과 M개를 처리하는 반복문이 있다. 마지막으로 result 값을 정렬하는 Collections.sort는 시간 복잡도를 O(klogk) (k는 result 안의 요소 갯수) 가지기 때문에 O(N + M + klogk)를 가진다.

추가로 문제를 풀 때, 사전순 정렬을 잘 보고 풀어야겠다.

문제푼 흔적