Hash Map을 이용한 Java 개수 세기 문제 풀이

1. 개요

개수 세기 문제(counting problem)는 어디나 나타납니다: 문자 빈도 세기, 가장 자주 나타나는 원소 찾기, 조건을 만족하는 쌍의 개수 세기, 같은 원소들을 그룹화하기. HashMap은 조회와 업데이트 모두 평균 O(1)이기 때문에 이 유형의 문제에 거의 “필수적인” 도구입니다.

이 글을 읽고 나면 HashMap(그리고 Map.merge, getOrDefault)을 사용해 4가지 일반적인 개수 세기 문제를 푸는 방법, 시간/공간 복잡도를 이해하고, 개수 세기 문제에서 HashMap을 사용할 때 흔히 마주치는 몇 가지 오류를 피할 수 있게 될 것입니다.

2. HashMap이 개수 세기에 적합한 이유

개수 세기 문제의 일반적인 아이디어: 각 원소마다 “지금까지 몇 번 나왔는지” 또는 “나왔는지 여부”를 알아야 합니다. HashMap<K, V>는 다음을 제공합니다:

• 평균 O(1)의 키 조회 — 정렬이 필요 없습니다.
• 값 업데이트(카운터 증가)를 평균 O(1)에 처리합니다.
• containsKey나 카운트 > 0으로 “본 것” 상태를 저장합니다.

정수 범위가 작고 미리 알 수 있을 때만 사용할 수 있는 카운팅 배열(counting array)과 달리, HashMap은 더 범용적입니다: 키는 String, Integer, 임의의 객체가 될 수 있습니다.

3. 원소의 빈도 세기

3.1. getOrDefault 사용

이것이 리스트의 각 원소 빈도를 세는 전형적인 방법입니다.

import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FrequencyCounter {

    public static Map<String, Integer> countFrequency(List<String> words) {
        Map<String, Integer> freq = new HashMap<>();
        for (String word : words) {
            freq.put(word, freq.getOrDefault(word, 0) + 1);
        }
        return freq;
    }
}

freq.getOrDefault(word, 0)은 word가 이미 존재하면 현재 값을 반환하고, 없으면 0을 반환합니다 — if (map.containsKey(...))를 쓸 필요가 없습니다. 리스트 ["cam", "xoai", "cam", "cam", "xoai"]에 대해 결과는:

{cam=3, xoai=2}

3.2. Map.merge 사용(더 짧은 코드)

Java 8부터 Map.merge는 확인과 업데이트를 하나의 호출로 결합합니다.

public static Map<String, Integer> countFrequencyMerge(List<String> words) {
    Map<String, Integer> freq = new HashMap<>();
    words.forEach(word -> freq.merge(word, 1, Integer::sum));
    return freq;
}

freq.merge(word, 1, Integer::sum)의 의미는: word가 없으면 1을 설정하고, 있으면 기존 값에 1을 더합니다(함수 Integer::sum을 통해). 이 방식은 약간 더 빠르고 단순한 누적 로직에서는 더 자연스럽게 읽힙니다.

3.3. JUnit 5 + AssertJ로 테스트

import org.junit.jupiter.api.Test;
import java.util.List;
import java.util.Map;
import static org.assertj.core.api.Assertions.assertThat;

class FrequencyCounterTest {

    @Test
    void shouldCountFrequencyCorrectly() {
        Map<String, Integer> result = FrequencyCounter.countFrequency(
                List.of("cam", "xoai", "cam", "cam", "xoai"));

        assertThat(result)
                .containsEntry("cam", 3)
                .containsEntry("xoai", 2);
    }
}

주의: getOrDefault는 키가 없을 때 맵을 수정하지 않습니다 — 읽기만 합니다. putIfAbsent와 헷갈리지 마세요. 이는 키가 없을 때 기본값을 설정하는 목적으로 사용됩니다.

4. 가장 자주 나타나는 원소 찾기

빈도 테이블을 만든 후 가장 자주 나타나는 원소를 찾는 것은 단지 entrySet()을 한 번 순회하는 것일 뿐입니다.

import java.util.Map;
import java.util.Optional;

public class MostFrequentFinder {

    public static Optional<String> findMostFrequent(Map<String, Integer> freq) {
        return freq.entrySet().stream()
                .max(Map.Entry.comparingByValue())
                .map(Map.Entry::getKey);
    }
}

Map.Entry.comparingByValue()는 엔트리를 값(나타난 횟수) 기준으로 비교하고, .max(...)는 가장 큰 값을 가진 엔트리를 가져옵니다. 여러 원소가 동등하게 가장 자주 나타나면 그중 하나만 반환합니다 — HashMap이 삽입 순서를 유지하지 않기 때문에 순서는 보장되지 않습니다.

입력:  {cam=3, xoai=2}
출력: Optional[cam]

주의: 동등하게 높은 순위의 여러 원소가 있을 때 결과가 안정적이어야 하면 HashMap 대신 LinkedHashMap을 사용하세요.

5. 조건을 만족하는 쌍 개수 세기(Two Sum 스타일)

일반적인 변형: arr[i] + arr[j] == target을 만족하는 쌍 (i, j)의 개수를 세기. O(n²) 완전탐색 대신 HashMap을 사용해 O(n)으로 줄입니다.

import java.util.HashMap;
import java.util.Map;

public class PairCounter {

    public static int countPairsWithSum(int[] numbers, int target) {
        Map<Integer, Integer> seen = new HashMap<>();
        int count = 0;

        for (int number : numbers) {
            int complement = target - number;
            count += seen.getOrDefault(complement, 0);
            seen.merge(number, 1, Integer::sum);
        }
        return count;
    }
}

각 줄 설명:

• complement = target - number: number와 더해 target을 만들 값.
• count += seen.getOrDefault(complement, 0): complement가 지금까지 나타난 횟수를 더합니다 — 각각이 하나의 유효한 쌍을 만듭니다.
• seen.merge(number, 1, Integer::sum): 현재 number를 카운팅 테이블에 기록하여 이후 원소들이 이와 쌍을 이룰 수 있도록 합니다.

numbers = [1, 2, 3, 2, 4]이고 target = 5일 때: 쌍은 (1,4), (2,3), (3,2)입니다 — 하지만 우리는 나타난 순서에 따라만 세기 때문에 테스트로 확인하세요.

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class PairCounterTest {

    @Test
    void shouldCountPairsWithGivenSum() {
        int[] numbers = {1, 2, 3, 2, 4};

        int result = PairCounter.countPairsWithSum(numbers, 5);

        assertThat(result).isEqualTo(3);
    }
}

3개의 쌍은: 숫자 3을 만날 때 (2,3), 두 번째 숫자 2를 만날 때 (2,3)(이미 본 3과 쌍), 그리고 4를 만날 때 (1,4)입니다.

6. 같은 원소 그룹화(애너그램 그룹)

더 고급 개수 세기 문제: 서로 애너그램인 단어들(같은 문자 집합이지만 순서가 다른)을 그룹화한 후 그룹 수 또는 각 그룹의 원소 수를 세기.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class AnagramGrouper {

    public static Map<String, List<String>> groupAnagrams(List<String> words) {
        Map<String, List<String>> groups = new HashMap<>();

        for (String word : words) {
            char[] chars = word.toCharArray();
            Arrays.sort(chars);
            String signature = new String(chars);

            groups.computeIfAbsent(signature, key -> new ArrayList<>())
                  .add(word);
        }
        return groups;
    }
}

핵심은 signature입니다: 각 단어의 문자를 정렬하여 모든 애너그램의 “서명”을 만듭니다. computeIfAbsent(signature, key -> new ArrayList<>())는 시그니처에 해당하는 키가 없으면 새 리스트를 만들고, 현재 단어를 추가합니다.

입력 ["eat", "tea", "tan", "ate", "nat", "bat"]에 대해 결과:

{
  "aet"=[eat, tea, ate],
  "ant"=[tan, nat],
  "abt"=[bat]
}

import org.junit.jupiter.api.Test;
import java.util.List;
import java.util.Map;
import static org.assertj.core.api.Assertions.assertThat;

class AnagramGrouperTest {

    @Test
    void shouldGroupAnagramsTogether() {
        Map<String, List<String>> groups = AnagramGrouper.groupAnagrams(
                List.of("eat", "tea", "tan", "ate", "nat", "bat"));

        assertThat(groups.values())
                .anySatisfy(group -> assertThat(group).containsExactlyInAnyOrder("eat", "tea", "ate"));
    }
}

computeIfAbsent는 수동 containsKey + put 확인보다 깔끔하며, 특히 값이 초기화가 필요한 컬렉션일 때 유용합니다(lazy init).

7. 시간 및 공간 복잡도

문제	시간	공간
빈도 세기	O(n)	O(k) — k는 서로 다른 원소의 개수
최빈원소 찾기	O(n)	O(k)
합이 target인 쌍 세기	O(n)	O(n)
애너그램 그룹화	O(n · m log m) — m은 가장 긴 단어의 길이	O(n)

먼저 정렬한 후 순회하는 해법과(O(n log n)) 비교하면, HashMap은 보통 시간 복잡도에서 더 빠르지만 추가 공간 O(n) 또는 O(k)가 필요합니다. 메모리가 제한적이고 키 범위가 작으면 카운팅 배열이 여전히 더 경제적인 선택입니다.

8. 흔한 실수

• 변경 가능한 객체를 키로 사용하면서 equals/hashCode를 오버라이드하지 않기: 자정의 클래스(예: Point)에 따라 세기를 할 때 이 두 메서드를 오버라이드하지 않으면 HashMap이 두 객체가 “같은”지를 같은 키로 인식하지 못합니다.

public record Point(int x, int y) {}

record를 사용하면 모든 필드를 기반으로 자동으로 equals/hashCode를 생성하여 이 오류를 완전히 피합니다.

• 반복 순서가 안정적이라고 기대하기: HashMap은 순서를 보장하지 않습니다. 삽입 순서가 필요하면 LinkedHashMap을 사용하고, 키의 오름차순이 필요하면 TreeMap을 사용하세요.

• entrySet()을 순회하는 중에 맵 수정하기: ConcurrentModificationException을 발생시킵니다. 순회 중에 항목을 제거해야 하면 Iterator.remove() 또는 removeIf를 사용하세요.

• 큰 루프에서 Integer 박싱을 신중하지 않게 사용하기: getOrDefault + + 1을 할 때마다 자동 박싱으로 새로운 Integer 객체가 만들어집니다. 매우 큰 데이터의 경우(백만 개의 원소), Map<String, int[]> 또는 원시 맵 라이브러리(예: Eclipse Collections) 사용을 고려하여 오버헤드를 줄이세요.

주의: 키 범위가 a-z 26자만이거나 작은 고정 정수 범위이면 배열(int[26])이 항상 더 빠르고 더 적은 메모리를 사용합니다. HashMap은 키 범위가 클 때, 미리 알 수 없을 때, 또는 연속적이지 않을 때만 사용하세요.

9. 결론

HashMap은 개수 세기 문제 — 빈도 세기, 최빈원소 찾기, 쌍 개수 세기, 같은 원소 그룹화 — 을 O(1) 조회 덕분에 단순한 O(n) 루프로 변환합니다. getOrDefault, merge, computeIfAbsent 메서드는 수동 containsKey 확인에 비해 코드를 더 간단하고 명확하게 만듭니다. 기억하세요: HashMap은 순서를 유지하지 않으며, 키 객체에 올바른 equals/hashCode가 필요하고, 키 범위가 작으면 카운팅 배열이 여전히 더 가벼운 선택입니다.