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

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

1764번: 듣보잡

1. 코드

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		Set <String> set = new HashSet<>();
		while(N-- > 0)
			set.add(sc.next());
		
		Set <String> answer = new TreeSet<>();
		while(M-- > 0) {
			String name = sc.next();
			if(set.contains(name))
				answer.add(name);
		}
		
		System.out.println(answer.size());
		for(String s : answer)
			System.out.println(s);
	}
}

2. 설명

Set <String> set = new HashSet<>();
while(N-- > 0)
    set.add(sc.next());

 듣도 못한 사람의 목록을 HashSet에 저장합니다.

Set <String> answer = new TreeSet<>();
while(M-- > 0) {
    String name = sc.next();
    if(set.contains(name))
        answer.add(name);
}

보도 못한 사람들 중 듣도 못한 사람에 속하는지 확인 후 속한다면 TreeSet에 추가합니다. TreeSet은 이진 탐색 구조로 추가할 때 오름차순으로 저장됩니다.

3. 정리

1. HashSet과 TreeSet을 적절히 활용
2. TreeSet은 이진 탐색 구조로 추가할 때 오름차순으로 저장