📜 PS 01 - HashMap 기초와 빈도수 문제

1주차 1일차 - HashMap 기초와 빈도수 문제

오늘 목표는:

“HashMap을 자유롭게 사용할 수 있는 수준”

까지 가는 것이다.

코딩테스트에서 HashMap은: 사실상 가장 중요한 자료구조 중 하나다.

특히 Java 백엔드 개발자라면:

• 빈도수 계산
• 중복 제거
• Key 기반 조회
• 캐시 구조

등을 매우 자주 사용하게 된다.

---

오늘 학습 목표

오늘 집중할 내용:

• HashMap 기본 동작 이해
• Key/Value 구조 이해
• 빈도수 문제 적응
• containsKey/get 활용
• 시간복잡도 감각 익히기

---

HashMap 핵심 개념

HashMap은:

Key 기반 빠른 조회를 제공하는 자료구조

다.

내부적으로는:

• hashCode 계산
• Bucket 저장
• equals 비교

방식으로 동작한다.

평균 시간복잡도:

O(1)

수준.

---

왜 HashMap이 중요한가?

코딩테스트에서 가장 자주 등장하는 패턴:

• 빈도수 계산
• 중복 체크
• 빠른 탐색

이기 때문이다.

예시:

• 완주하지 못한 선수
• 베스트앨범
• 의상
• 전화번호 목록

등.

---

대표 문제 유형 1 - 빈도수 계산

가장 기본 패턴.

예시:

• 특정 숫자가 몇 번 등장했는가?
• 가장 많이 등장한 문자열은?

---

핵심 접근 방식

핵심 사고 흐름:

“등장 횟수를 저장해야 한다”

라면:

HashMap<Key, Count>

구조를 떠올려야 한다.

---

Java 코드 예시

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

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

---

getOrDefault가 중요한 이유

매우 자주 사용된다.

기존 방식:

if (map.containsKey(key)) {
    map.put(key, map.get(key) + 1);
} else {
    map.put(key, 1);
}

개선:

map.put(key, map.getOrDefault(key, 0) + 1);

훨씬 간결하다.

---

대표 문제 유형 2 - 중복 제거

HashSet과 함께 자주 등장.

예시:

• 중복 문자 제거
• 중복 숫자 제거

---

핵심 포인트

Hash 기반 자료구조는:

조회 속도가 빠르다

따라서: 중복 체크 최적화에 매우 강하다.

---

대표 문제 유형 3 - Key 기반 탐색

예시:

• 전화번호 목록
• 영어 단어 매칭
• 캐릭터 이름 조회

---

시간복잡도 관점

잘못된 방식:

O(N²)

대표 예시:

for + for 중첩 탐색

---

HashMap 사용 시

대부분:

O(N)

수준까지 감소 가능.

이것이 HashMap의 가장 큰 장점이다.

---

왜 조회가 빠를까?

HashMap은:

hashCode 기반 Bucket 접근

을 수행한다.

따라서: 배열 인덱스처럼 접근 가능하다.

---

실무형 관점

HashMap은 실무에서도 매우 많이 사용된다.

대표 사례:

• 캐시
• 사용자 세션
• 메모리 기반 조회
• API 응답 매핑

즉:

코딩테스트 + 실무

둘 다 핵심 자료구조다.

---

자주 하는 실수

1. NullPointerException

잘못된 코드:

map.get(key) + 1

key가 없으면 null 반환 가능.

---

해결

map.getOrDefault(key, 0)

사용.

---

2. containsKey 남용

너무 많이 사용하면: 코드가 길어지고 가독성이 떨어진다.

---

3. 시간복잡도 계산 실수

HashMap은 평균:

O(1)

이지만:

최악의 경우:

O(N)

가능성 존재.

다만 실전에서는 대부분 평균 성능 기준으로 사용한다.

---

Trade-off 관점

HashMap 장점

• 빠른 조회
• 빠른 삽입
• 빈도수 계산 최적

---

단점

• 정렬 보장 안 됨
• 메모리 사용량 증가 가능
• hash 충돌 가능성 존재

---

다른 자료구조와 비교

Array

장점:

• 메모리 효율 좋음

단점:

• 탐색 느림

---

HashMap

장점:

• 탐색 빠름

단점:

• 메모리 추가 사용

즉:

“속도 vs 메모리”

Trade-off 존재.

---

면접에서 설명한다면?

예시 답변:

빈도수 계산이 필요한 문제였기 때문에 빠른 조회가 가능한 HashMap을 사용했습니다. 평균 시간복잡도를 O(1) 수준으로 줄일 수 있어 전체 탐색 성능을 개선할 수 있었습니다.

정도까지 설명 가능하면 좋다.

---

추천 문제

프로그래머스

• 완주하지 못한 선수
• 전화번호 목록
• 의상
• 베스트앨범

---

백준

• 숫자 카드
• 문자열 집합

---

추천 풀이 순서

Step 1

• 완주하지 못한 선수

가장 기본적인 빈도수 문제.

---

Step 2

• 전화번호 목록

Hash 기반 탐색 감각 익히기.

---

Step 3

• 베스트앨범

HashMap + 정렬 조합 연습.

---

실전 팁

코딩테스트에서:

“빠른 탐색이 필요한가?”

싶으면:

가장 먼저 HashMap 사용 가능성을 떠올려야 한다.

이것만으로도: 문제 접근 속도가 크게 빨라진다.

---

핵심 요약

오늘 핵심은 다음이다.

• HashMap은 코딩테스트 핵심 자료구조
• 빈도수 계산 문제 매우 중요
• 평균 시간복잡도 O(1)
• getOrDefault 반드시 익숙해질 것
• 빠른 조회 문제에서 HashMap 우선 고려

특히 중요한 건:

“왜 HashMap을 선택했는가”

를 설명할 수 있는 수준까지 가는 것이다.