[백준] 듣보잡 (HashSet, HashMap, getOrDefault, contains, sort, 1764번, Java)

q

 

문제설명

입력 & 출력

나의 풀이

 

이번 문제는 듣도 못한 사람 N과 보도 못한 사람 M이 주어질 때 듣도 못한 사람 + 보도 못한 사람 = "듣도보도 못한 사람"을 구하는 문제입니다.

 

먼저 빠른 입력을 위해서 Buffer로 입력을 받아주고, StringTokenizer를 사용하여 N과M을 공백을 기준으로 분리하여 각각 저장해줍니다.

 

저는 N과 M의 입력을 한 번에 받아서 듣지도 보지도 못한 사람은 vlaue가 2가 형성되도록 구성했습니다.

 

HashMap을 선언해 주고, N과 M을 입력을 받고, getOrDefault() 메서드를 사용하여 해당하는 이름을 1씩 증가했습니다.

 

 

이러면 듣도 보도 못한 사람은 위 실행결과와 같이 value가 2가 형성됩니다.

 

그리고 keySet() 메서드와 get() 메서드를 사용하여 value가 2 이상인 사람의 이름을 ArrayList에 넣어줍니다.

 

그리고 ❗️문제에서 요구한 대로 "듣보잡의 수와 그 명단을 사전순으로 출력한다."를 만족하기 위하여 Collections의 sort() 메서드를 사용하여 리스트를 사전순으로 정렬해 줍니다.

 

마지막으로 리스트의 크기와 이름을 출력하며 마무리해줍니다.

 

 

 

refactoring ✅

 

전체적인 로직은 "나의 풀이"와 동일하지만 이번 코드는 "나의 풀이"처럼 HashMap이 아니라 HashSet을 사용하고, contains() 메서드를 사용했습니다.

 

Set에 듣지도 못한 사람을 추가해 주고, ArrayList를 선언한 뒤 Set의 contains() 메서드를 사용하여 보도 못한 사람이 Set에 존재하는지 확인합니다.

 

만약 Set에 존재한다면 듣도 못하면서 보도 못한 사람 즉 "듣보잡"입니다.

 

---

 

• 1번 ➡️ HashSet
• 2번 ➡️ HahsMap

---

• 1번 코드에서는 듣도 보도 못한 사람들의 정보를 모두 HashMap에 저장하고, 중복 여부를 확인하면서 추가 작업을 수행합니다.
  • 이 때 HashMap의 put, getOrDefault 메서드는 평균적으로 O(1)의 시간 복잡도를 가지므로, 전체 시간 복잡도는 O(N + M)입니다.

 

• 2번 코드에서는 듣도 못한 사람(N)을 HashSet에 저장하고, 보도 못한 사람(M)을 확인할 때 contains 메서드를 사용합니다.
  • HashSet의 contains 메서드도 평균적으로 O(1)의 시간 복잡도를 가집니다. 따라서 전체 시간 복잡도도 O(N + M)입니다.

 

 

두 코드 모두 시간 복잡도 면에서는 유사하며, 특정 상황에서는 HashSet을 사용한 두 번째 코드가 약간 더 빠를 수 있습니다. 이는 HashSet이 내부적으로 해시 함수를 사용하여 더 빠르게 검색할 수 있기 때문입니다.

 

하지만 이 차이는 입력의 크기가 매우 클 때에만 두드러지며, 보통은 미비한 차이입니다.

 

 

참고❗️

[JAVA] 입출력, BufferedReader, StringTokenizer, StringBuilder 알아보기

[JAVA] HashMap 이란 ❓ (1/2)

[JAVA] HashSet 클래스 사용법 (중복 없는 데이터 집합)

 

[JAVA] ArrayList 알아보기 (동적 배열)