Ch.3 해시맵과 해시셋

면접 실전: HashMap으로 푸는 5가지 패턴

Two Sum, Group Anagrams 등 대표 HashMap 문제 5가지를 풀 수 있다문제 유형별로 어떤 해시맵 패턴을 적용해야 하는지 판단한다

코딩 면접 HashMap 문제, 패턴만 알면 절반은 끝입니다

Two Sum, Group Anagrams, Top K Frequent, Valid Sudoku, Longest Consecutive — 이 5가지 패턴이 면접 HashMap 문제의 80%를 커버합니다.

패턴은 알겠는데, 실전에서 어떤 패턴을 써야 할지 어떻게 판단하지?

각 패턴의 '신호'를 읽는 법을 익히면 문제를 보자마자 해시맵을 꺼낼 수 있습니다.

lightbulb

핵심 개념

보수(complement) 탐색

target - num을 해시맵에서 O(1)로 찾는 기법

한 패스 해시맵

순회하면서 동시에 해시맵에 저장하는 패턴

article

핵심 내용

Two Sum: 배열에서 합이 target이 되는 두 수의 인덱스를 찾아라

def two_sum(nums: list[int], target: int) -> list[int]:
    seen = {}  # 값 → 인덱스 매핑
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:       # O(1) 탐색!
            return [seen[complement], i]
        seen[num] = i                # 현재 값 저장
    return []

# nums = [2, 7, 11, 15], target = 9
print(two_sum([2, 7, 11, 15], 9))  # [0, 1]

Two Sum 핵심: • 신호: "두 수의 합/차" → 보수 탐색 • 시간: O(n), 공간: O(n) • 패턴: 순회하며 seen에 저장 + complement 탐색

문자열 배열에서 아나그램끼리 묶어라! 키를 어떻게 만들 것인가가 핵심

from collections import defaultdict

def group_anagrams(strs: list[str]) -> list[list[str]]:
    groups = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))  # 정렬하면 아나그램은 같은 키!
        groups[key].append(s)
    return list(groups.values())

# 입력: ["eat", "tea", "tan", "ate", "nat", "bat"]
# 출력: [["eat","tea","ate"], ["tan","nat"], ["bat"]]
print(group_anagrams(["eat","tea","tan","ate","nat","bat"]))

핵심 아이디어: sorted("eat") = sorted("tea") = ['a','e','t'] → 같은 키!

Group Anagrams 핵심: • 신호: "그룹핑", "아나그램" → 키 변환 + defaultdict(list) • 시간: O(n·k log k) (k = 문자열 최대 길이) • 패턴: 변환된 키로 그룹핑

배열에서 가장 자주 등장하는 k개를 찾아라! Counter의 진가를 발휘할 차례

from collections import Counter

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    count = Counter(nums)
    return [num for num, freq in count.most_common(k)]

# 입력: nums = [1,1,1,2,2,3], k = 2
print(top_k_frequent([1,1,1,2,2,3], 2))  # [1, 2]
# Bucket Sort 방식 — O(n) 풀이
def top_k_frequent_bucket(nums: list[int], k: int) -> list[int]:
    count = Counter(nums)
    # 인덱스 = 빈도수, 값 = 해당 빈도수의 숫자들
    buckets = [[] for _ in range(len(nums) + 1)]
    for num, freq in count.items():
        buckets[freq].append(num)

    result = []
    for i in range(len(buckets) - 1, -1, -1):  # 높은 빈도부터
        for num in buckets[i]:
            result.append(num)
            if len(result) == k:
                return result
    return result

Top K 핵심: • 신호: "가장 자주", "상위 k개" → Counter + most_common • 빠른 풀이: Counter.most_common(k) — O(n log n) • 최적 풀이: Bucket Sort — O(n)

스도쿠 보드가 유효한지 검증하라! set으로 중복을 감지하는 패턴

def is_valid_sudoku(board: list[list[str]]) -> bool:
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]

    for r in range(9):
        for c in range(9):
            num = board[r][c]
            if num == ".":
                continue

            box_idx = (r // 3) * 3 + (c // 3)

            if num in rows[r] or num in cols[c] or num in boxes[box_idx]:
                return False  # 중복 발견!

            rows[r].add(num)
            cols[c].add(num)
            boxes[box_idx].add(num)

    return True

Valid Sudoku 핵심: • 신호: "중복 없는지 확인" → set으로 중복 감지 • 시간: O(1) — 9×9 고정 크기 • 패턴: 행/열/박스마다 set 유지

정렬 없이 가장 긴 연속 수열의 길이를 찾아라! O(n)으로 가능할까?

def longest_consecutive(nums: list[int]) -> int:
    num_set = set(nums)  # O(1) 조회용
    longest = 0

    for num in num_set:
        # 시퀀스의 시작점만 탐색! (num-1이 없으면 시작점)
        if num - 1 not in num_set:
            current = num
            length = 1
            while current + 1 in num_set:  # O(1) 확인
                current += 1
                length += 1
            longest = max(longest, length)

    return longest

# [100, 4, 200, 1, 3, 2] → 연속: 1,2,3,4 → 길이 4
print(longest_consecutive([100, 4, 200, 1, 3, 2]))  # 4

Longest Consecutive 핵심: • 신호: "연속", "정렬 없이" → set + 시작점 탐색 • 시간: O(n) — 각 숫자를 최대 2번만 방문 • 트릭: num-1이 없는 숫자만 시작점으로 탐색

문제를 읽고 어떤 패턴을 써야 할지 판단하는 법을 정리합니다

Two Sum에서 nums=[3,3], target=6일 때 seen 딕셔너리에 처음 저장되는 항목은?

Longest Consecutive에서 '시작점'을 판별하는 조건은?

HashMap 5패턴 정복!

key

핵심 용어

①

Two Sum

보수(complement) 탐색 — 가장 기본

②

Group Anagrams

키 변환 + 그룹핑

③

Top K Frequent

Counter + 정렬/힙

④

Valid Sudoku

set으로 중복 감지

⑤

Longest Consecutive

set + 시퀀스 시작점 탐색

🔍

두 수의 합/차

→ 보수 탐색 (Two Sum 패턴)

📂

그룹핑/분류

→ 키 변환 + defaultdict(list)

📊

빈도수/상위 k개

→ Counter + most_common

❌

중복 확인

→ set에 넣고 in 연산

📏

연속 수열

→ set + 시작점 탐색

edit_note

정리 노트

면접 HashMap 5패턴 총정리

패턴 요약

① Two Sum
보수 탐색 — target-num을 seen에서 O(1) 조회
② Group Anagrams
키 변환 — sorted(s)를 키로 defaultdict(list)
③ Top K Frequent
Counter + most_common(k) 또는 Bucket Sort
④ Valid Sudoku
set 중복 감지 — 행/열/박스별 set 유지
⑤ Longest Consecutive
set + 시작점 — num-1 없으면 시작, 확장 탐색
★

면접관에게 '이 문제는 Two Sum 패턴의 변형입니다'라고 말하면 +10점!

image

시각 자료

다이어그램: ds-d22
다이어그램: ds-d24
check_circle

핵심 정리

  • 1Two Sum → 보수 탐색 패턴
  • 2Group Anagrams → 키 변환 + 그룹핑 패턴
  • 3Top K / Sudoku / Longest Consecutive → Counter, set 활용

퀴즈와 인터랙션으로 더 깊이 학습하세요

play_circle인터랙티브 레슨 시작