HashSet 가이드 (3/3)

이전 편: [코딩테스트] 2. HashSet 활용 패턴

이 문서가 시리즈의 마지막 편입니다.

HashSet과 HashMap은 둘 다 해시 기반 자료구조다. 차이는 저장하는 정보다.

자료구조저장하는 것질문
HashSet<T>값 자체이 값이 있는가
HashMap<K, V>키와 값이 키에 대응되는 정보가 무엇인가

존재 여부면 HashSet

값이 한 번이라도 등장했는지만 필요하면 HashSet이 맞다.

Set<String> set = new HashSet<>();

for (String word : words) {
    set.add(word);
}

return set.contains(target);

예시:

  • 문자열 집합에 포함되는지 확인
  • 서로 다른 종류의 개수 세기
  • 이미 방문한 좌표인지 확인

개수면 HashMap

같은 값이 몇 번 등장했는지 필요하면 HashMap<T, Integer>가 맞다.

Map<String, Integer> count = new HashMap<>();

for (String name : participant) {
    count.put(name, count.getOrDefault(name, 0) + 1);
}

예시:

  • 동명이인 처리
  • 문자 빈도 비교
  • 숫자 등장 횟수 세기
  • 두 배열의 원소 구성이 같은지 비교

완주하지 못한 선수에 적용하기

이 문제는 해시 문제지만 HashSet만으로는 부족하다. 이유는 동명이인 때문이다.

participant = ["mislav", "stanko", "mislav", "ana"]
completion  = ["stanko", "ana", "mislav"]

HashSet으로 바꾸면 참가자 쪽도 완주자 쪽도 "mislav"가 있다는 사실만 남는다. 참가자에 "mislav"가 2명이라는 정보가 사라진다.

그래서 이 문제는 다음처럼 봐야 한다.

필요한 정보자료구조
이름이 있는가HashSet
이름이 몇 명인가HashMap<String, Integer>

정답에 필요한 것은 "몇 명인가"이므로 HashMap을 쓴다.

선택 기준 표

문제 문장떠올릴 구조
"서로 다른", "종류 수", "중복 제거"HashSet
"존재하는지", "포함되는지"HashSet
"몇 번", "개수", "빈도"HashMap<T, Integer>
"이름별 점수", "키별 상태"HashMap<K, V>
"순서대로 출력"List, 정렬, LinkedHashSet
"정렬된 상태 유지"TreeSet, TreeMap

외우는 법

Set은 값만 기억한다. 그래서 답할 수 있는 질문이 단순하다.

Set: 너 있었어?
Map: 너 몇 번 있었어? 너의 값은 뭐야?

문제에서 답이 존재 여부로 끝나면 HashSet이다. 존재 여부를 넘어 개수나 상태가 붙으면 HashMap이다.

HashMap 카운팅 기본형

Map<String, Integer> count = new HashMap<>();

for (String key : arr) {
    count.put(key, count.getOrDefault(key, 0) + 1);
}

감소까지 필요하면 다음처럼 쓴다.

for (String key : arr2) {
    count.put(key, count.get(key) - 1);
}

마지막에 0이 아닌 값을 찾으면 차이를 알 수 있다.

for (String key : count.keySet()) {
    if (count.get(key) != 0) {
        return key;
    }
}

관련 문서