[백준 1764번] 듣보잡

www.acmicpc.net/problem/1764

1764번: 듣보잡

 

해싱 자료구조를 이용하는 문제입니다.

자바에서 지원하는 Hash 자료구조를 사용할 경우, 자료구조에 저장되는 커스텀 객체는 hashcode(), equals() 를 필수로 오버라이딩 해야합니다. String의 경우 이미 구현되어 있기 때문에 그대로 사용하면 됩니다.

 

문제 해결 방법은 집합 A,B 중 하나를 골라 모두 해시 자료 구조에 저장합니다. 그리고 다른 집합의 원소들이 해시 자료 구조에 포함되어 있는지 하나씩 살펴보면 됩니다. 이렇게 풀면 시간복잡도는 O(N)이 됩니다.

 

이 문제에서는 공간 복잡도도 고려해볼 필요가 있습니다. 문제에서 문자열은 최대 20자 이하로 주어지고 하나의 집합의 크기는 최대 500000입니다. String 역시 내부의 char의 배열로 이루어져 있으므로 20자 이하라면 최대 40바이트가 됩니다(char = 2바이트).

40 * 500000 = 2천만이 되는데 2천만 바이트는 20MB 이므로 512MB의 제한보다 훨씬 아래네요.

 

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

public class Main {
	static int n,m;
	static List<String> dontHeard = new ArrayList<>();
	public static void main(String[] args) throws IOException {
//		InputReader reader = new InputReader("testcase.txt");
		InputReader reader = new InputReader();
		StringTokenizer st = new StringTokenizer(reader.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		HashSet<String> dontLook = new HashSet<>();
		for (int i = 0; i < n; i++) {
			dontLook.add(reader.readLine());
		}

		for (int i = 0; i < m; i++) {
			dontHeard.add(reader.readLine());
		}

		dontHeard.sort(Comparator.naturalOrder());
//		System.out.println(dontHeard);
		List<String> ret = dontHeard.stream()
				.filter(s -> dontLook.contains(s))
				.collect(Collectors.toList());
		System.out.println(ret.size());
		ret.forEach(s -> System.out.println(s));
	}
}

class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
	public Long readLong() throws IOException {
		return Long.parseLong(readLine());
	}
}