[Baekjoon] 1764번: 듣보잡 - Java

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

1764번: 듣보잡

문제 설명

듣도 못한 사람 N명과 보도 못한 사람 M명을 입력받고 두 리스트에 모두 포함되는 사람의 명수와 이름을 정렬해서 출력하며 된다.

풀이 방법 1. 이중 반복문 - 시간 초과

N과 M의 최대 크기가 500,000씩이어서 이중 반복문으로 풀면 시간 초과가 날 것 같았고 역시나 시간 초과가 발생했다.

deudbojabs = Stream.of(deudjabs)
    .filter((deudjab) -> Stream.of(bojabs).anyMatch(Predicate.isEqual(deudjab))).sorted()
    .collect(Collectors.toList());

풀이 방법 2. HashSet - 통과

듣도 못한 사람을 HashSet에 저장하고 보도 못한 사람을 입력받은 후 HashSet에 존재하는지 판단하는 방법으로 변경했다. HashSet의 경우 해시테이블 기반으로 요소의 접근 시간 복잡도가 O(1)이다. 즉 HashSet에 존재하는지 판단하는 속도도 O(1)이다. 따라서 O(n^2)인 이중 반복문에 비해 훨씬 빠르게 문제를 해결할 수 있다.

Set<String> deudjabs = new HashSet<>();

List<String> deudbojabs = IntStream.range(0, M)
    .mapToObj(idx -> () -> br.readLine())
    .filter(deudjabs::contains).sorted().collect(Collectors.toList());

전체 코드는 다음과 같다.

package baekjoon.string;

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

public class BOJ1764 {

    static Set<String> deudjabs;

    static int N;
    static int M;

    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int[] persons =
                    Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            N = persons[0];
            M = persons[1];

            deudjabs = new HashSet<>();

            IntStream.range(0, N)
                    .forEach(idx -> throwingRunnableWrapper(() -> deudjabs.add(br.readLine())));

            StringBuilder sb = new StringBuilder();

            List<String> deudbojabs = IntStream.range(0, M)
                    .mapToObj(idx -> throwingSupplierWrapper(() -> br.readLine()))
                    .filter(deudjabs::contains).sorted().collect(Collectors.toList());

            sb.append(deudbojabs.size()).append("\n");
            deudbojabs.forEach(deudbojab -> sb.append(deudbojab).append("\n"));
            sb.deleteCharAt(sb.length() - 1);

            System.out.print(sb);
        }
    }

    @FunctionalInterface
    public interface ThrowingRunnable<E extends Exception> {
        void run() throws E;
    }

    static void throwingRunnableWrapper(ThrowingRunnable<Exception> throwingRunnable) {
        try {
            throwingRunnable.run();
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }

    @FunctionalInterface
    public interface ThrowingSupplier<T, E extends Exception> {
        T get() throws E;
    }

    static <T> T throwingSupplierWrapper(ThrowingSupplier<T, Exception> throwingSupplier) {
        try {
            return throwingSupplier.get();
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }
}