[JAVA/백준] 1764번: 듣보잡(구현, 정렬) - HashSet

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

1764번: 듣보잡

 

 

풀이

HastSet을 이용해 듣도 못한 사람의 집단에 보도 못한 사람이 포함되는지 아닌지 판단할 수 있다.

 - HasbSet.contains() 

정답은 List에 담아서 저장한다.

 

듣도 못한 사람을 입력받고 HashSet에 저장한다. => hs.add()

그 후 보도 못한 사람을 입력받을 때 마다, 듣도 못한 사람을 저장한 HashSet에 있는경우 List에 저장한다.

최종적으로 명단을 사전순으로 출력하므로, List를 정렬하고 듣보잡의 수는 리스트의 크기인 size()가 된다.

 

ArrayList로 contains()를 사용할 수도 있지만, 시간초과가 발생한다. 시간초과를 잡기 위해서는 HashSet을 사용해야한다.

 

 

코드

 

 

정리

알고리즘 분류 - 자료구조, 문자열, 정렬

난이도 - Sliver 4

 

 

 

📝오늘의 메모

HashSet의 contains()는 O(1),  ArrayList의 contains()는 O(n)이다.

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

ArrayList를 사용하면 시간초과가 날 수 있는데, 효율성이 필요한 문제라면 HashSet을 사용해야겠다.