[알고리즘] 12. 빈도수 계산
지난 글에서는 카운팅 배열에 대해 정리했습니다. 이번 글에서는 알고리즘 문제에서 정말 자주 등장하는 빈도수 계산에 대해 알아보겠습니다.
빈도수 계산은 어떤 값이 몇 번 등장했는지 세는 작업입니다. 숫자, 문자, 문자열, 단어 등 다양한 데이터를 대상으로 사용할 수 있습니다.
빈도수 계산은 데이터가 몇 번 등장했는지 기록하고, 그 횟수를 이용해 문제를 해결하는 방법입니다.
1. 빈도수 계산이란?
빈도수는 어떤 값이 등장한 횟수를 의미합니다. 예를 들어 다음 숫자 배열이 있다고 생각해보겠습니다.
1 2 2 3 3 3 4각 숫자의 빈도수는 다음과 같습니다.
| 값 | 빈도수 |
|---|---|
| 1 | 1번 |
| 2 | 2번 |
| 3 | 3번 |
| 4 | 1번 |
이처럼 각 값이 몇 번 나왔는지 세는 것이 빈도수 계산입니다.
2. 빈도수 계산이 필요한 상황
알고리즘 문제에서는 단순히 값이 있는지 확인하는 것뿐 아니라, 몇 번 등장했는지를 알아야 하는 경우가 많습니다.
- 가장 많이 등장한 값 찾기
- 중복된 값 확인하기
- 한 번만 등장한 값 찾기
- 문자별 등장 횟수 세기
- 단어별 등장 횟수 세기
- 두 배열의 구성 요소가 같은지 확인하기
- 조건에 맞는 빈도수만 골라내기
빈도수 계산은 단독으로도 많이 사용되지만, 정렬, 해시, 문자열 처리 문제와 함께 나오는 경우도 많습니다.
3. 카운팅 배열로 빈도수 계산하기
값의 범위가 작고 정해져 있다면 카운팅 배열을 사용할 수 있습니다. 예를 들어 숫자가 1부터 5까지만 나온다면 count 배열로 충분합니다.
int[] numbers = {1, 2, 2, 3, 3, 3, 4};
int[] count = new int[6];
for (int i = 0; i < numbers.length; i++) {
count[numbers[i]]++;
}
for (int i = 1; i < count.length; i++) {
if (count[i] > 0) {
System.out.println(i + "의 빈도수: " + count[i]);
}
}출력 결과는 다음과 같습니다.
1의 빈도수: 1
2의 빈도수: 2
3의 빈도수: 3
4의 빈도수: 1카운팅 배열은 값 자체를 인덱스로 사용하기 때문에 매우 빠릅니다. 특정 값의 등장 횟수도 count[값]으로 바로 확인할 수 있습니다.
값의 범위가 작고 명확하다면 카운팅 배열이 가장 단순하고 빠릅니다.
4. HashMap으로 빈도수 계산하기
값의 범위가 크거나, 숫자가 아닌 문자열을 세어야 한다면 HashMap을 사용하는 것이 좋습니다.
HashMap은 key와 value를 함께 저장하는 자료구조입니다. 빈도수 계산에서는 보통 key에 값, value에 등장 횟수를 저장합니다.
key: 실제 값
value: 등장 횟수import java.util.HashMap;
int[] numbers = {10, 20, 10, 30, 20, 10};
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < numbers.length; i++) {
int num = numbers[i];
map.put(num, map.getOrDefault(num, 0) + 1);
}
System.out.println(map);출력 결과는 순서가 다를 수 있지만, 내용은 다음과 같습니다.
{20=2, 10=3, 30=1}10은 3번, 20은 2번, 30은 1번 등장했습니다.
5. getOrDefault() 이해하기
HashMap으로 빈도수를 계산할 때 자주 사용하는 메서드가 getOrDefault()입니다.
map.put(num, map.getOrDefault(num, 0) + 1);이 코드는 처음 보면 복잡해 보이지만 의미는 단순합니다.
- num이 이미 map에 있으면 기존 횟수를 가져온다.
- num이 처음 나온 값이면 기본값 0을 사용한다.
- 가져온 값에 1을 더해서 다시 저장한다.
예를 들어 숫자 10이 처음 등장했다면 다음처럼 동작합니다.
map.getOrDefault(10, 0) → 0
0 + 1 → 1
map.put(10, 1)숫자 10이 다시 등장했다면 기존 값 1을 가져와서 2로 갱신합니다.
map.getOrDefault(10, 0) → 1
1 + 1 → 2
map.put(10, 2)getOrDefault()는 값이 없을 때 사용할 기본값을 정해주는 메서드입니다.
6. 문자열의 문자 빈도수 계산하기
문자열에서 각 문자가 몇 번 등장했는지 세는 문제도 자주 나옵니다. 알파벳 소문자만 나온다면 카운팅 배열을 사용할 수 있습니다.
String word = "banana";
int[] count = new int[26];
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
count[ch - 'a']++;
}
for (int i = 0; i < count.length; i++) {
if (count[i] > 0) {
char ch = (char) ('a' + i);
System.out.println(ch + ": " + count[i]);
}
}출력 결과는 다음과 같습니다.
a: 3
b: 1
n: 2소문자 알파벳은 ch - 'a'를 이용해 0부터 25까지의 인덱스로 바꿀 수 있습니다.
7. HashMap으로 문자 빈도수 계산하기
문자 범위가 알파벳으로 제한되어 있지 않거나, 한글, 숫자, 기호가 섞일 수 있다면 HashMap을 사용하는 편이 더 유연합니다.
import java.util.HashMap;
String text = "hello";
HashMap<Character, Integer> map = new HashMap<>();
for (int i = 0; i < text.length(); i++) {
char ch = text.charAt(i);
map.put(ch, map.getOrDefault(ch, 0) + 1);
}
System.out.println(map);출력 결과는 순서가 다를 수 있지만, 내용은 다음과 같습니다.
{e=1, h=1, l=2, o=1}HashMap은 값의 범위를 미리 알기 어려울 때 편리합니다.
8. 단어 빈도수 계산하기
빈도수 계산은 문자뿐 아니라 단어에도 사용할 수 있습니다. 문장을 공백 기준으로 나눈 뒤, 각 단어가 몇 번 나왔는지 세어보겠습니다.
import java.util.HashMap;
String sentence = "java spring java sql spring java";
String[] words = sentence.split(" ");
HashMap<String, Integer> map = new HashMap<>();
for (int i = 0; i < words.length; i++) {
String word = words[i];
map.put(word, map.getOrDefault(word, 0) + 1);
}
System.out.println(map);출력 결과는 다음과 비슷합니다.
{spring=2, java=3, sql=1}java는 3번, spring은 2번, sql은 1번 등장했습니다.
단어 빈도수 계산은 split()과 HashMap을 함께 사용하는 경우가 많습니다.
9. 가장 많이 등장한 값 찾기
빈도수 계산 후에는 가장 많이 등장한 값을 찾아야 하는 문제가 자주 나옵니다. HashMap을 순회하면서 value가 가장 큰 key를 찾으면 됩니다.
import java.util.HashMap;
import java.util.Map;
int[] numbers = {10, 20, 10, 30, 20, 10};
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : numbers) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
int maxValue = 0;
int maxCount = 0;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
int value = entry.getKey();
int count = entry.getValue();
if (count > maxCount) {
maxCount = count;
maxValue = value;
}
}
System.out.println("가장 많이 등장한 값: " + maxValue);
System.out.println("등장 횟수: " + maxCount);출력 결과는 다음과 같습니다.
가장 많이 등장한 값: 10
등장 횟수: 3여기서 key는 실제 값이고, value는 등장 횟수입니다. 이 둘을 헷갈리지 않는 것이 중요합니다.
10. 한 번만 등장한 값 찾기
빈도수 계산을 이용하면 한 번만 등장한 값도 쉽게 찾을 수 있습니다. 등장 횟수가 1인 값을 찾으면 됩니다.
import java.util.HashMap;
import java.util.Map;
int[] numbers = {1, 2, 2, 3, 3, 4};
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : numbers) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() == 1) {
System.out.println("한 번만 등장한 값: " + entry.getKey());
}
}출력 결과는 다음과 같습니다.
한 번만 등장한 값: 1
한 번만 등장한 값: 4중복을 제거하거나 유일한 값을 찾는 문제에서 자주 사용되는 방식입니다.
11. 중복 여부 확인하기
어떤 값이 중복으로 등장했는지도 빈도수 계산으로 확인할 수 있습니다. 등장 횟수가 2 이상인 값이 있으면 중복입니다.
import java.util.HashMap;
import java.util.Map;
int[] numbers = {5, 1, 3, 1, 4};
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : numbers) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
boolean hasDuplicate = false;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() >= 2) {
hasDuplicate = true;
break;
}
}
System.out.println(hasDuplicate);출력 결과는 다음과 같습니다.
true숫자 1이 두 번 등장했기 때문에 중복이 있다고 판단할 수 있습니다.
12. 카운팅 배열과 HashMap 비교
빈도수 계산에서는 카운팅 배열과 HashMap을 자주 비교하게 됩니다. 둘 다 등장 횟수를 세는 데 사용할 수 있지만, 적합한 상황이 다릅니다.
| 구분 | 카운팅 배열 | HashMap |
|---|---|---|
| 사용 조건 | 값의 범위가 작고 명확함 | 값의 범위가 크거나 다양함 |
| 대상 | 주로 정수, 알파벳 | 정수, 문자, 문자열 등 |
| 속도 | 매우 빠름 | 대체로 빠름 |
| 메모리 | 값의 범위만큼 필요 | 등장한 값 위주로 저장 |
| 예시 | 1~100 점수 개수 세기 | 단어별 등장 횟수 세기 |
값의 범위가 작으면 카운팅 배열이 좋고, 범위가 크거나 문자열이 섞이면 HashMap이 좋습니다.
빈도수 계산에서는 값의 범위를 먼저 보고 카운팅 배열과 HashMap 중 하나를 선택하면 됩니다.
13. 빈도수 계산의 시간복잡도
빈도수 계산은 보통 데이터를 한 번 순회하면서 처리합니다. 입력 개수를 N이라고 하면 기본 시간복잡도는 O(N)입니다.
for (int num : numbers) {
map.put(num, map.getOrDefault(num, 0) + 1);
}이 반복문은 numbers 배열의 모든 값을 한 번씩 확인합니다. 따라서 시간복잡도는 O(N)입니다.
이후 HashMap 전체를 한 번 더 순회한다면, 서로 다른 값의 개수를 K라고 할 때 O(K)가 추가됩니다.
| 작업 | 시간복잡도 |
|---|---|
| 빈도수 계산 | O(N) |
| 빈도수 결과 확인 | O(K) |
| 전체 | O(N + K) |
보통 K는 N보다 작거나 같기 때문에, 전체적으로 효율적인 방식입니다.
14. 빈도수 계산에서 자주 하는 실수
빈도수 계산 문제에서는 아래 실수를 조심해야 합니다.
- 값의 범위를 확인하지 않고 카운팅 배열을 만드는 경우
- count 배열 크기를 최댓값보다 작게 만드는 경우
- HashMap에서 key와 value를 헷갈리는 경우
- getOrDefault()의 기본값을 잘못 설정하는 경우
- 문자 카운팅에서 ch - 'a' 또는 ch - 'A'를 빼먹는 경우
- 문자열을 split()할 때 기준 문자를 잘못 사용하는 경우
- 최빈값을 찾을 때 등장 횟수와 실제 값을 반대로 저장하는 경우
특히 HashMap에서는 key와 value의 의미를 정확히 잡아야 합니다.
key → 실제 데이터 값
value → 등장 횟수빈도수 계산의 핵심은 무엇을 key로 저장하고, 무엇을 value로 저장할지 정하는 것입니다.
15. 정리
이번 글에서는 빈도수 계산에 대해 정리했습니다.
- 빈도수 계산은 값이 몇 번 등장했는지 세는 작업이다.
- 값의 범위가 작고 명확하면 카운팅 배열을 사용할 수 있다.
- 값의 범위가 크거나 문자열을 다룰 때는 HashMap이 유용하다.
- HashMap에서는 key에 실제 값, value에 등장 횟수를 저장한다.
- getOrDefault()를 사용하면 빈도수를 간단히 갱신할 수 있다.
- 문자, 숫자, 단어 빈도수 계산에 모두 활용할 수 있다.
- 최빈값, 중복 여부, 한 번만 등장한 값 찾기에 자주 사용된다.
빈도수 계산은 알고리즘 문제에서 정말 많이 쓰이는 기본 패턴입니다. 문제를 보고 “몇 번 나왔는지 세야 한다”는 생각이 들면 카운팅 배열이나 HashMap을 먼저 떠올리면 됩니다.
빈도수 계산은 데이터를 한 번 훑으면서 등장 횟수를 기록하는 강력한 기본기입니다.
다음 글 예고
다음 글에서는 정렬 기준 만들기에 대해 알아보겠습니다.
숫자 정렬, 문자열 정렬, 객체 정렬, Comparator를 이용한 여러 조건 정렬까지 차근차근 정리해보겠습니다.
'Problem Solving > Algorithm' 카테고리의 다른 글
| [알고리즘] 14. 예외 케이스 처리법 (0) | 2026.06.27 |
|---|---|
| [알고리즘] 13. 정렬 기준 만들기 (0) | 2026.06.26 |
| [알고리즘] 11. 카운팅 배열 (0) | 2026.06.24 |
| [알고리즘] 10. 숫자 처리와 자리수 (0) | 2026.06.24 |
| [알고리즘] 09. 문자열 자르기와 비교 (0) | 2026.06.24 |