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 처리를 해주어야 합니다. 또한 같은 키를 입력할 경우 기존 값이 덮어씌워지는데, 누적이 필요한 상황에서는 누적 처리를 해주어야 합니다.