백준1764_듣보잡 (java)

생각한 문제풀이 방식

• 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M
• N과 M은 각각 최대 500,000이므로 N+M은 100만이다. 제한시간은 2초이므로 시간복잡도는 O(N^2)미만이 되야한다.
• 먼저, HashMap을 사용해서 듣도못한 사람의 이름을 key로 횟수를 value로 저장. 처음 이름이 나오는 것이기때문에 value를 1로 지정
• 그리고 보도못한 사람의 명단을 돌면서 map에 이미 이름이 있으면 +1
• 모든 입력을 받고 난 후 map에서 value가 2에 해당하는 key의 갯수와 이름을 출력해준다.

해당 자료구조를 사용한 이유

• 자료구조는 HashMap을 사용했다. 듣도못한 사람과 보도못한 사람의 명단이 순서대로 입력되는데 그 중에서 듣도보도 못한사람이란 뜻은 두 그룹에 모두 속해있다는 뜻이다.
• 각 명단에는 중복되는 이름이 없기 때문에 최종적으로 각 이름이 몇번 나왔는지를 세어보면 두번을 넘는 값은 없을 것이고, 이 문제에서는 각 이름이 몇번 나왔는지만 중요하기 때문에 순서도 상관없다.
• 결론적으로 이름(key)별로 횟수(value)를 세어 각 명단 두 곳에서 모두 나왔는지만 보면 되고 순서는 상관없기에 HashMap을 사용했다.

코드

import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in); // 입력과 출력을 BufferedReader와 StringBuilder를 쓰면 더 빨라진다.

		int N = sc.nextInt();
		int M = sc.nextInt();

		HashMap<String, Integer> map = new HashMap<String, Integer>();
		sc.nextLine();

		for(int i=0; i<N+M; i++) {
			String name = sc.nextLine();
			map.put(name, map.getOrDefault(name, 0) + 1);
		}

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

		for(String key : map.keySet()) {
			if(map.get(key) == 2) list.add(key);
		}
		Collections.sort(list);
		
		System.out.println(list.size());
		for(int i=0; i<list.size(); i++) {
			System.out.println(list.get(i));	
		}
	}
}

 

시간 복잡도 분석 O(NlogN) - 수도코드

map = new HashMap<String, Integer>();
sb = new StringBuilder

int n = input();
int m = input();

for(int i=0; i<n+m; i++)  // O(N+M)
	name = input();
	map.put(name, map.getOrDefault(name, 0) + 1);

ArrayList<String> list = new ArrayList<String>();
for(String key : map.keySet()) // O(N)
	if(map.get(key) == 2) list.add(key);

list.sort(); // O(NlogN)

sb.append(list.size());
for(String x : list) 
	sb.append(x);

알게된 점

Collections.sort()는 Timsort()라는 정렬기법을 사용한다.

여기서 Timsort란 삽입 정렬과 합병정렬을 결합하여 만든 정렬이라고한다. Timsort의 시간복잡도는 평균 O(n log(n)) 이며 최악의 경우도 O(n log(n)) 이라고한다.

 

해당 알고리즘을 공부하면서 Timesort에 대해 알게되었으므로 해당 정렬기법에 대해 좀 더 자세히 알아봐야겠다.