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

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

1764번: 듣보잡

 

---

문제는 정말 간단하다

 

듣도 못한 사람 N명의 명단을 받은 다음

보도 못한 사람 M명의 명단을 입력받으면서, 듣도보도 못한 명단에 포함 된 사람이면 기록해뒀다가 출력하면 된다.

 

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.PriorityQueue;
import java.util.StringTokenizer;

public class P1764 {

	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());

		HashSet<String> set = new HashSet<>();
		PriorityQueue<String> pq = new PriorityQueue<>();

		for (int i = 0; i < n; i++) {
			set.add(br.readLine());
		}

		for (int i = 0; i < m; i++) {
			String str = br.readLine();
			if (set.contains(str)) {
				pq.add(str);
			}
		}

		int rs=pq.size();
		System.out.println(rs);
		for (int i = 0; i < rs; i++) {
			System.out.println(pq.poll());
		}
	}

}

N,M이 최대 50만이기 때문에 O(n^2)으로는 시간초과가 날 것이라 예상했다. (대략적으로 시간복잡도 1억==1초라고 한다)

 

그런데 contains()메소드가 어느 자료구조라도 시간복잡도가 O(n)일 것이라고 생각을 했고(사실은 그게 아니었지만)

시간초과가 날것같지만 어찌할 방법을 찾지 못해 일단 ArrayList로 작성을 했었고,

그 코드는 시간초과가 났다.

 

알고보니 HashSet에서는 contains()메소드의 시간복잡도가 O(1)이었다.

그래서 ArrayList로 작성했던 코드를 Hashset으로 바꿔서 작성하니 시간초과가 나지 않았다.