2주차

HashMap / Set

개념

Set 또는 Map은 인터페이스로 실제로 구현되지 않는 추상메서드만 가지고 있습니다. 이 추상메서드를 구현한 것이 HashSet, HashMap 같은 클래스입니다. 위 사진에서 다양한 클래스들을 확인할 수 있습니다.
Set과 HashMap은 저장 단위와 중복 허용 등의 차이가 있기 때문에 둘의 차이를 이해하고 문제 풀이에 더 적합한 방법을 찾는 것이 중요합니다.

HashMap

HashMap은 키(key) 와 값(value) 쌍을 저장하는 자료구조입니다. 각 키는 고유하며 키를 사용해 원하는 값을 빠르게 검색할 수 있습니다.
HashMap은 자료구조로 배열(Array)을 사용하는데, 해싱을 통해 변환된 해시코드는 배열의 각 요소인 버킷(Bucket)의 인덱스가 됩니다. 이 인덱스를 통해 값을 빠르게 찾을 수 있습니다.

해싱은 키(key)를 해싱 함수(Hashing Function)를 이용해 정수값인 해시코드(Hashcode)로 변환하는 것을 말합니다.

특징

• 키를 사용해 빠른 액세스 가능
• 키의 순서 보장하지 않음
• 키 중복 불가, 값 중복 가능
• 해싱 충돌 발생 가능

키는 숫자뿐만 아니라 문장까지도 가능해 그 수는 무궁무진합니다. 그러나 인덱스는 배열의 크기보다 작은 정수로 한정되어 있어 많은 키가 있다면 서로 다른 키가 동일한 인덱스를 가질 가능성이 있습니다. 이렇게 서로 다른 키가 동일한 해시 코드를 갖는 것을 해싱 충돌(Hashing Collision)이라고 합니다.

해싱 충돌 해결 방법

• 체이닝(Chaining)
• 개방 주소법 (Open Addressing)
• 재해싱 (Rehashing)
• 버킷 확장 (Bucket Expansion)
• 커스텀 해시 함수 사용

Set

Set은 수학적 집합과 유사하게 동작하는 추상 자료형입니다. 주로 빠른 검색, 삽입, 삭제 연산을 위해 사용됩니다. HashMap과 다르게 키를 저장하지 않고 값만 저장합니다.

특징

• 중복된 요소 허용하지 않음
• 순서 없음 -> 자동 정렬X
• 집합 연산 제공

Set은 언제 사용할까?

1. 중복된 데이터를 허용하지 않으면서 빠른 검색, 삽입, 삭제가 필요한 경우
   ex) 사용자 ID 목록 관리
2. 특정 값 존재 여부 판단할 경우
3. 중복된 데이터 제거해야 하는 경우

Set의 시간 복잡도

• 삽입, 삭제, 검색, 크기 확인 => O(1)
• 합집합/교집합/차집합 계산 => O(n)

문제 패턴

HashMap을 활용하는 문제 패턴

1. 빈도 계산

• 문자열/배열에서 각 원소의 등장 횟수 세기
  ex) 문자열에서 가장 많이 등장한 문자를 구하라

2. 매핑 구조

• 키-값 관계를 빠르게 조회
  ex) 학생 이름->점수 매핑 후 특정 학생 점수 찾기

3. 인덱스 추적

• 배열에서 값과 인덱스를 매핑해 빠르게 위치 찾기
  ex) 두 수의 합이 target이 되는 인덱스 찾기

4. 그래프 표현

• 인접 리스트 구현 (노드->연결된 노드 리스트)

5. 캐싱

• 최근 조회한 값을 저장해 빠르게 다시 접근

Set을 활용하는 문제 패턴

1. 중복 제거

• 배열이나 문자열에서 중복된 원소 제거
  ex) 배열에서 유니크한 숫자만 남겨라

2. 존재 여부 확인

• 특정 값이 이미 등장했는지 빠르게 체크
  ex) 두 배열에 공통된 원소가 있는지 확인하라

3. 집합 연산

• 교집합, 합집합, 차집합 구현
  ex) 두 문자열에 공통된 문자 찾기

4. 사이클 탐지

• 그래프나 연결리스트에서 방문한 노드를 기록해 중복 망문 여부 확인

결론!!

• 중복/존재 여부 -> Set
• 빈도/매핑/인덱스 -> HashMap

예시 문제 기반 설명

https://school.programmers.co.kr/learn/courses/30/lessons/42576

이 문제는 참가자 명단과 완주자 명단이 주어지고 참가자 중 완주하지 못한 선수를 찾는 문제입니다. 동명이인이 존재할 수 있으므로 참가자 명단 단순 소거가 아닌 빈도를 계산해야 하기 때문에 HashMap을 사용해 풀어줍니다.

Java

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        Map<String, Integer> map = new HashMap<>();

        // 참가자 카운트
        for (String p : participant) {
            map.put(p, map.getOrDefault(p, 0) + 1);
        }

        // 완주자 카운트 감소
        for (String c : completion) {
            map.put(c, map.get(c) - 1);
        }

        // 값이 0이 아닌 키가 완주하지 못한 선수
        for (String key : map.keySet()) {
            if (map.get(key) != 0) {
                return key;
            }
        }
        return "";
    }
}

Python

def solution(participant, completion):
    dic = {}

    # 참가자 카운트
    for p in participant:
        dic[p] = dic.get(p, 0) + 1

    # 완주자 카운트 감소
    for c in completion:
        dic[c] -= 1

    # 값이 0이 아닌 키 반환
    for key, value in dic.items():
        if value != 0:
            return key

• 파이썬은 딕셔너리가 HashMap과 같은 기능을 함

JavaScript

function solution(participant, completion) {
    const map = new Map();

    // 참가자 카운트
    for (let p of participant) {
        map.set(p, (map.get(p) || 0) + 1);
    }

    // 완주자 카운트 감소
    for (let c of completion) {
        map.set(c, map.get(c) - 1);
    }

    // 값이 0이 아닌 키 반환
    for (let [key, value] of map) {
        if (value !== 0) return key;
    }
}

실수 포인트

순서 착각

HashMap과 Set은 모두 순서가 없는데 출력 시 순서가 보장될거라고 생각할 수 있습니다.

시간 복잡도

평균적으로는 시간복잡도가 _O(1)_이지만 최악의 경우 _O(n)_이 될 수 있어 런타임 에러가 날 수 있습니다.

HashMap 키 처리

키만 존재하고 값이 없는 경우에는 null 처리를 해주어야 합니다. 또한 같은 키를 입력할 경우 기존 값이 덮어씌워지는데, 누적이 필요한 상황에서는 누적 처리를 해주어야 합니다.