[코딩테스트] 전화번호부 문제: HashSet, HashMap, 정렬

전화번호부 문제(프로그래머스 42577)는 어떤 전화번호가 다른 번호의 접두사인지 확인하는 문제이다. 이번 글에서는 정렬과 해시를 활용한 효율적인 풀이법과 HashSet vs HashMap 선택 기준을 정리한다.

---

1. 정렬 후 인접 원소 비교

핵심 아이디어

• 전화번호를 사전순으로 정렬하면, 접두사 관계가 발생하는 번호는 반드시 인접한 두 원소 사이에서만 확인 가능
• 따라서 모든 쌍을 비교할 필요 없이, 옆 번호만 확인하면 된다.

시간 복잡도

• 정렬: O(n log n)
• 인접 비교: O(n*k) (k = 문자열 길이)
• 전체: O(n log n + n * k)

// github 예시 코드: BOJ_42577_해시
Arrays.sort(phone_book);
for (int i = 0; i < phone_book.length - 1; i++) {
	if (phone_book[i+1].startsWith(phone_book[i])) return false;
}    

---

2. HashSet을 활용한 접두사 탐색

핵심 아이디어

• 모든 전화번호를 HashSet에 저장
• 각 번호의 prefix를 하나씩 잘라서 존재 여부를 확인
• HashSet은 평균 O(1)로 조회 가능

시간 복잡도

• 각 번호 길이 k만큼 prefix 확인 -> O(n * k)

// github 예시 코드: BOJ_42577_Hash
HashSet<String> set = new HashSet<>(Arrays.asList(phone_book));
for (String number : phone_book) {
	for (int i = 1; i < number.length(); i++) {
    	if (set.contains(number.substring(0, i))) return false;
    }
}

주의

• substring으로 문자열 객체가 반복 생성됨
  • 실무에서 대규모 데이터를 다루는 경우, 성능을 고려해야 함

---

HashSet vs HashMap

• HashSet
  • 저장방식: key만, Value는 내부 더미 객체
  • 용도: 존재 여부 확인
    • 중복 제거, 방문여부 체크(Visited)
• HashMap
  • 저장방식: Key-Value 쌍 저장
  • 용도: 키와 연관된 추가 정보가 필요 시
    • 빈도수 세기(Counting), 빠른검색(Dictionary)

결론: 존재 여부만 확인하면 HashSet, 값까지 관리해야 하면 HashMap

---

java에서의 사용

---

활용 포인트

1. 전체 비교 대신 정렬이나 자료구조 선택으로 범위를 최소화한다
2. 존재 여부 확인 -> HashSet 사용
3. 추가 정보 관리 필요 -> HashMap 사용
4. 문자열 관계 문제 -> 정렬/해시/Trie 선택

---

🔗 참고

• 깃허브코드: BOJ42577_Hash해시1 & 2