#1764: 듣보잡 [JAVA]

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

1764번: 듣보잡

 

 

---

 

 

 

 

 

문제 접근

 

 

 

 

1. List 클래스의 교집합 메소드인 retainsAll() 썼으나 시간 초과

2. ArrayList의 contains() 메소드 쓰니까 시간 초과

 

3. HashSet 사용 성공 !

 

 

 

 

 

HashSet의 contains()는 O(1), ArrayList의 contains()는 O(n)이다. HashSet은 map을 기반으로 구현되고 ArrayList는 indexOf()를 사용해서 contain여부를 결정한다.

 

[ 참고 ] https://hanul-dev.netlify.app/java/list,-set-%EC%96%B4%EB%96%A4-%EA%B2%83%EC%9D%84-%EC%93%B0%EB%8A%94-%EA%B2%83%EC%9D%B4-%EC%9C%A0%EB%A6%AC%ED%95%9C%EA%B0%80/

 

 

 

 

 

 

 

 

코드

 

 

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		Set<String> set = new HashSet<>();
		while (n-- > 0) {
			set.add(br.readLine());
		}

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

		while (m-- > 0) {
			String name = br.readLine();
			if (set.contains(name)) { // 시간 중요!
				list.add(name);
			}
		}

		Collections.sort(list);

		StringBuilder sb = new StringBuilder();
		sb.append(list.size()).append('\n');

		for (String s : list) {
			sb.append(s).append('\n');
		}

		System.out.println(sb);
	}
}