[백준/자바] 1764번: 듣보잡

문제

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

풀이

• 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때
• 듣도 보도 못한 사람의 명단을 구하라
  • 듣도 못한 사람의 명단에 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지

		names = new HashSet<>();
		for (int i = 0; i < n; i++) {
			names.add(br.readLine());
		}

• 듣도 못한 사람의 명단만 입력을 받아 저장해 줍니다.

		answer = new ArrayList<>();
		for (int i = 0; i < m; i++) {
			String name = br.readLine();
			if (names.contains(name)) answer.add(name);
		}

• 보도 못한 사람의 명단이 주어질 때마다, 듣도 못한 사람의 명단에 이름이 있는지 비교합니다.
• 만약 존재한다면 정답 배열에 추가

마쳤다면 출력해주면 끝입니다.

이 문제에서 왜 HashSet을 썼냐?

배열에 듣도 못한 사람의 명단을 넣고 보도 못한 사람의 명단을 입력 받을 때마다 탐색을 해주면 O(N)의 시간을 더 쓰게 됩니다.
그렇게 되면 시간초과가 발생하죠.
하지만 HashSet에 넣어주면, contains()로 탐색을 할 때 O(1)이라는 짧은 시간만 걸려 훨씬 효율적이게 됩니다.

코드

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

public class Main_1764 {
	static StringBuilder sb = new StringBuilder();
	static int n, m;
	static Set<String> names;
	static List<String> answer;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		names = new HashSet<>();
		for (int i = 0; i < n; i++) {
			names.add(br.readLine());
		}
		
		answer = new ArrayList<>();
		for (int i = 0; i < m; i++) {
			String name = br.readLine();
			if (names.contains(name)) answer.add(name);
		}
		
		Collections.sort(answer);
		sb.append(answer.size() + "\n");
		for (String n : answer) sb.append(n + "\n");
		System.out.println(sb.toString());
	}

}