Map 활용

도입

코딩테스트에서 Map은 “빠르게 찾고, 세고, 묶고, 기억하는” 문제를 푸는 핵심 도구다

코딩테스트에서 Map은 단순한 자료구조가 아니라 문제 해결 패턴 그 자체로 자주 등장합니다. 특정 값이 몇 번 나왔는지 세거나, 어떤 값을 본 적이 있는지 기록하거나, 값에 해당하는 다른 정보를 즉시 찾는 문제는 대부분 Map으로 매우 효율적으로 풀 수 있습니다.

특히 자바에서는 HashMap, TreeMap, LinkedHashMap을 상황에 맞게 선택하고, getOrDefault, putIfAbsent, computeIfAbsent, merge 같은 메서드를 적절히 활용하면 코드 길이도 줄고 실수도 크게 줄일 수 있습니다.

필요성

Map을 잘 다루면 O(n²) 문제를 O(n) 또는 O(n log n) 수준으로 줄일 수 있는 경우가 많다

배열이나 리스트만으로 문제를 풀면 두 겹 반복문이 필요한 경우가 많습니다. 하지만 Map을 이용하면 “찾는 과정”을 빠르게 바꿀 수 있어서, 시간 복잡도를 크게 줄일 수 있습니다.

Map이 강한 문제 유형

• 빈도 수 세기
• 중복 체크
• 특정 값의 첫 위치 / 마지막 위치 저장
• 두 수의 합 / 짝 찾기
• 누적합 빈도 기반 부분합 문제
• 그룹핑
• 정렬된 키 관리가 필요한 문제

구현체 선택

코딩테스트에서는 대부분 HashMap이 기본이고, 정렬이 필요할 때만 TreeMap을 의심하면 된다

구현체	언제 쓰나
HashMap	대부분의 일반적인 문제
TreeMap	키 정렬이 바로 필요할 때
LinkedHashMap	입력 순서 유지가 답에 영향을 줄 때

자주 쓰는 메서드

getOrDefault, putIfAbsent, computeIfAbsent, merge를 익혀두면 Map 문제 풀이가 훨씬 짧고 안전해진다

map.getOrDefault(key, 0);              // 없으면 기본값 사용
map.putIfAbsent(key, value);           // 키 없을 때만 넣기
map.computeIfAbsent(key, k -> new ArrayList<>()); // 없으면 생성
map.merge(key, 1, Integer::sum);       // 누적 더하기

실전 팁

코딩테스트에서는 NullPointerException 방지를 위해 get()보다 getOrDefault()를 먼저 떠올리는 습관이 좋습니다.

패턴 1. 빈도 수 세기

가장 많이 나오는 Map 패턴은 “값 → 등장 횟수” 형태의 카운팅이다

문자열, 숫자, 문자, 이름 등 어떤 값이 몇 번 나왔는지 세는 문제는 거의 항상 Map으로 풀립니다.

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

for (String word : words) {
    freq.put(word, freq.getOrDefault(word, 0) + 1);
}

자주 나오는 문제 형태

• 가장 많이 나온 수 찾기
• 문자열에서 각 문자 개수 세기
• 아나그램 판별
• 의상 종류별 개수 세기

패턴 2. 존재 여부 기록

어떤 값을 본 적이 있는지 빠르게 확인해야 할 때 Map 또는 Set이 핵심이 된다

어떤 값이 이미 등장했는지 여부만 중요하면 사실 Set이 더 적합한 경우도 많습니다. 하지만 “등장 여부 + 관련 정보”가 함께 필요하면 Map이 더 강력합니다.

Map<Integer, Boolean> visited = new HashMap<>();

for (int num : nums) {
    if (visited.containsKey(num)) {
        System.out.println("중복 발견");
    }
    visited.put(num, true);
}

패턴 3. 위치 기억하기

값의 첫 등장 위치나 마지막 위치를 기억해 두면 두 겹 반복문 없이 문제를 해결할 수 있다

숫자나 문자열이 처음 나온 위치, 마지막으로 나온 위치, 특정 값의 인덱스를 기억하는 문제는 Map이 매우 잘 맞습니다.

Map<Integer, Integer> firstIndex = new HashMap<>();

for (int i = 0; i < nums.length; i++) {
    firstIndex.putIfAbsent(nums[i], i);
}

관련 문제 유형

• 처음 등장한 위치 구하기
• 가장 가까운 같은 문자 찾기
• 중복 원소의 거리 계산

패턴 4. 짝 찾기 / Two Sum

현재 값의 보완값(complement)을 Map에서 즉시 찾는 방식은 대표적인 O(n) 패턴이다

가장 유명한 Map 패턴 중 하나가 바로 Two Sum입니다. 현재 숫자와 짝이 되는 값이 이전에 등장했는지 Map에서 즉시 확인하는 방식입니다.

Map<Integer, Integer> indexMap = new HashMap<>();

for (int i = 0; i < nums.length; i++) {
    int targetValue = target - nums[i];

    if (indexMap.containsKey(targetValue)) {
        return new int[]{indexMap.get(targetValue), i};
    }

    indexMap.put(nums[i], i);
}

이 패턴은 두 수의 합뿐 아니라, 차이, 보완값, 반대값, 특정 조건을 만족하는 이전 원소 찾기 문제에도 자주 확장됩니다.

패턴 5. 그룹핑

같은 기준을 가진 데이터를 하나의 리스트로 묶어야 할 때는 Map<K, List<V>> 패턴이 자주 등장한다

“같은 알파벳으로 시작하는 단어끼리”, “같은 종류끼리”, “같은 해시 결과끼리” 묶는 문제에서는 Map 안에 리스트를 넣는 패턴이 유용합니다.

Map<String, List<String>> group = new HashMap<>();

for (String s : words) {
    String key = s.substring(0, 1);
    group.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}

특히 computeIfAbsent()를 모르면 코드가 장황해지기 쉽기 때문에, 이 메서드는 꼭 익혀두는 것이 좋습니다.

패턴 6. 슬라이딩 윈도우 + 카운팅

구간 내 빈도 관리는 Map과 슬라이딩 윈도우를 결합하면 강력해진다

길이가 고정되거나 조건을 만족하는 구간을 움직이며 구간 안 원소들의 개수를 관리해야 할 때 Map이 자주 사용됩니다.

Map<Character, Integer> count = new HashMap<>();
int left = 0;

for (int right = 0; right < s.length(); right++) {
    char rc = s.charAt(right);
    count.put(rc, count.getOrDefault(rc, 0) + 1);

    while (count.get(rc) > 1) {
        char lc = s.charAt(left++);
        count.put(lc, count.get(lc) - 1);
        if (count.get(lc) == 0) count.remove(lc);
    }
}

관련 문제 유형

• 중복 없는 가장 긴 부분 문자열
• 특정 길이 구간의 문자 빈도 비교
• 아나그램 구간 개수

패턴 7. 누적합 빈도

부분합 문제는 “누적합 값이 몇 번 나왔는지”를 Map으로 관리하면 O(n)으로 줄어드는 경우가 많다

부분 배열 합, 특정 합을 만드는 구간 개수 문제에서는 현재 누적합과 과거 누적합의 관계를 이용합니다. 이때 과거 누적합 빈도를 Map으로 저장하면 매우 강력합니다.

Map<Integer, Integer> prefixCount = new HashMap<>();
prefixCount.put(0, 1);

int sum = 0;
int answer = 0;

for (int num : nums) {
    sum += num;
    answer += prefixCount.getOrDefault(sum - k, 0);
    prefixCount.put(sum, prefixCount.getOrDefault(sum, 0) + 1);
}

관련 문제 유형

• 부분합이 k인 구간 개수
• 나머지가 같은 누적합 개수
• 누적합 + 해시 응용 문제

패턴 8. 정렬된 키 관리

키를 정렬된 상태로 바로 다뤄야 할 때는 TreeMap이 깔끔한 해법이 된다

코딩테스트에서 “가장 작은 키”, “가장 큰 키”, “정렬된 출력”이 문제 조건에 직접 포함되면 HashMap보다 TreeMap이 더 자연스러울 수 있습니다.

TreeMap<Integer, Integer> map = new TreeMap<>();

for (int num : nums) {
    map.put(num, map.getOrDefault(num, 0) + 1);
}

System.out.println(map.firstKey());
System.out.println(map.lastKey());

패턴 9. 좌표 압축 / 값 매핑

값 자체를 다른 번호나 순위로 치환해야 하는 문제에서도 Map은 매우 유용하다

좌표 압축처럼 원래 값을 더 작은 정수 인덱스로 바꿔야 할 때는 정렬한 뒤 “원래 값 → 압축된 값”을 Map에 저장합니다.

int[] sorted = Arrays.stream(nums).distinct().sorted().toArray();
Map<Integer, Integer> rank = new HashMap<>();

for (int i = 0; i < sorted.length; i++) {
    rank.put(sorted[i], i);
}

패턴 10. 문자열 문제

문자열 문제에서 Map은 문자 빈도, 위치 기록, 패턴 비교에 매우 자주 사용된다

• 아나그램 확인 → 문자 빈도 Map
• 가장 많이 등장한 문자 → 카운팅 Map
• 이전 등장 위치 기록 → 문자별 최근 인덱스 Map
• 부분 문자열 빈도 비교 → 슬라이딩 윈도우 + Map

자주 하는 실수

코딩테스트에서 Map 문제를 틀리는 이유는 대개 null 처리, 업데이트 누락, 구조 선택 실수 때문이다

• get() 결과가 null인데 바로 연산해서 NullPointerException 발생
• 카운트 감소 후 0이 된 키를 제거하지 않아 로직 꼬임
• 정렬이 필요한데 HashMap을 쓰고 따로 처리 안 함
• 등장 여부만 필요해도 Map을 남용함 → Set이 더 단순할 수 있음
• 키와 값의 의미를 뒤집어 저장해서 로직이 복잡해짐

풀이 루틴

문제를 보면 “무엇을 키로 저장할지, 값에는 무엇을 넣을지”부터 정리하는 습관이 중요하다

1. 무엇을 기준으로 찾는지 먼저 본다.
2. 키는 무엇인지 정한다.
3. 값에는 개수 / 인덱스 / 리스트 / 합계 중 무엇이 들어가야 하는지 정한다.
4. 정렬이 필요 없으면 우선 HashMap부터 생각한다.
5. Null 처리 방지를 위해 getOrDefault나 putIfAbsent를 우선 사용한다.

디버깅

Map 풀이가 틀릴 때는 키 정의, 초기값, 업데이트 순서, 제거 조건을 먼저 확인해야 한다

1

키가 문제에서 요구하는 식별 기준과 정확히 일치하는지 확인한다.

2

초기값을 0으로 볼지 1로 볼지, 빈 Map에서 시작할지 미리 정의한다.

3

증가/감소 후 0이 되는 키를 제거해야 하는 문제인지 확인한다.

4

HashMap으로 충분한데 TreeMap을 써서 시간 초과가 나는 것은 아닌지 점검한다.

5

Map이 아니라 Set이나 배열 카운팅이 더 적합한 문제는 아닌지도 같이 본다.

요약

코딩테스트에서 Map은 “기억”, “집계”, “매핑”, “즉시 조회” 문제를 빠르게 푸는 가장 중요한 도구 중 하나다

• ✅ Map은 코딩테스트에서 O(n²)을 O(n) 수준으로 줄이는 핵심 도구가 될 수 있다.
• ✅ 기본 구현체는 HashMap, 정렬이 필요할 때는 TreeMap을 고려한다.
• ✅ 빈도 수, 위치 기억, 짝 찾기, 그룹핑, 누적합 문제에서 매우 자주 등장한다.
• ✅ getOrDefault, putIfAbsent, computeIfAbsent, merge를 익혀두면 코드가 짧고 안전해진다.
• ✅ 문제를 보면 “키에 무엇을 넣고, 값에 무엇을 넣을지”부터 정의하는 습관이 중요하다.

RELATED POST

Java HashMap만 따로 깊게 파는 버전
List / Set / Map 비교 통합본
코딩테스트에서 자주 나오는 빈도 수와 누적합 패턴 정리