맵과 셋을 활용한 빈도 기반 패턴
맵(Map)은 키별 값을 저장하는 구조이고, 셋(Set)은 존재 여부만 저장하는 구조입니다. 빈도 문제는 맵으로, 중복 판정은 셋으로 시작하면 풀이가 단순해집니다. 이 구분이 없으면 같은 문제를 이중 루프로 풀어 성능이 빠르게 나빠집니다.
또 하나 꼭 챙길 것은 키 정규화입니다. 대소문자, 공백, 포맷 차이를 우선 통일하지 않으면 같은 데이터가 다른 키로 나뉩니다. 여기서는 빈도 문제를 단계별로 정리해 코테에서 바로 재사용할 수 있게 구성합니다.
핵심 개념: 맵/셋과 키 정규화
맵/셋 문제는 구조 자체보다 입력을 어떤 키로 볼지 우선 정하면 훨씬 쉬워집니다. 코드를 보기 전에 현재 문제의 키 정규화 규칙을 한 줄로 적어 두세요.
맵(Map)은 키별로 값을 붙여 저장하는 구조입니다.
정확히는 고유 키에 대응하는 값을 관리하는 연관 배열(associative array)입니다.
{"apple": 2, "banana": 1}처럼 단어별 출현 횟수를 저장할 때 가장 자주 쓰입니다.
셋(Set)은 값의 존재 여부만 관리하는 구조입니다. 중복 없는 원소 집합을 저장해서 membership 질의를 빠르게 처리합니다. 이미 본 아이디를 셋에 넣고, 다시 같은 아이디가 나오면 즉시 중복으로 판정할 수 있습니다.
키 정규화는 같은 의미의 입력을 같은 형태로 통일하는 전처리입니다.
비교 전에 대소문자, 공백, 포맷을 일관된 규칙으로 변환해 키 분산 오류를 줄입니다.
" Apple "과 "apple"을 모두 "apple"로 맞춘 뒤 카운트하면 같은 데이터가 둘로 갈라지지 않습니다.
맵/셋 선택이 운영에 미치는 영향
빈도 문제를 매번 정렬이나 중첩 루프로 처리하면 비용이 빠르게 증가합니다.
맵/셋 패턴은 한 번 순회로 대부분의 통계 정보를 얻을 수 있어 실무에서 매우 자주 쓰입니다.
또한 로직이 분리돼 있어 요구사항 변경에 강합니다.
예: 단순 카운트에서 Top-K, 중복 제거, 필터링으로 쉽게 확장 가능합니다.
빈도 계산 디버깅 시나리오
여기서는 오답 -> 디버깅 -> 교정 -> 검증 흐름으로 추적해, 어디서 불변식이 깨지는지 단계별로 확인합니다.
문자열 빈도 집계를 손으로 한 번 따라가 보겠습니다.
- 입력:
["Apple", " apple ", "banana", "BANANA"] - 정규화 규칙: 소문자 + 양끝 공백 제거
Apple,apple은 모두apple로 통합됩니다.banana,BANANA는banana로 통합됩니다.- 최종 카운트는
apple:2,banana:2가 됩니다. - 정규화가 빠지면 같은 항목이 다른 키로 분리됩니다.
문자열 빈도와 중복 추출
문제 의도: 키 정규화 후 빈도 카운트와 중복 추출을 한 번에 수행합니다.
입력 예시: 문자열 목록 ["A", "a", " b ", "b"]
출력 예시: 빈도 맵과 중복 키 목록
freq[key] += 1은 해당 키의 개수를 1씩 누적하는 가장 기본적인 카운팅 패턴입니다.
#include <algorithm>
#include <cctype>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
string normalize(const string& s) {
string t;
for (char c : s) {
if (!isspace(static_cast<unsigned char>(c))) t.push_back(static_cast<char>(tolower(c)));
}
return t;
}
int main() {
vector<string> sample = {"API", "db", "api", "cache", "DB", "api", ""};
unordered_map<string, int> freq;
for (const auto& w : sample) {
string n = normalize(w);
if (!n.empty()) freq[n]++;
}
vector<string> dup;
for (const auto& kv : freq) {
if (kv.second >= 2) dup.push_back(kv.first);
}
sort(dup.begin(), dup.end());
for (const auto& kv : freq) cout << kv.first << ":" << kv.second << " ";
cout << "\n";
for (const auto& w : dup) cout << w << " ";
cout << "\n";
return 0;
}import java.util.*;
public class Main {
static String normalize(String s) {
return s.trim().toLowerCase();
}
public static void main(String[] args) {
List<String> sample = List.of("API", "db", "api", "cache", "DB", "api", "");
Map<String, Integer> freq = new HashMap<>();
for (String w : sample) {
String n = normalize(w);
if (!n.isEmpty()) freq.put(n, freq.getOrDefault(n, 0) + 1);
}
List<String> dup = new ArrayList<>();
for (Map.Entry<String, Integer> e : freq.entrySet()) {
if (e.getValue() >= 2) dup.add(e.getKey());
}
Collections.sort(dup);
System.out.println(freq);
System.out.println(dup);
}
}def analyze_words(words):
freq = {}
for w in words:
n = w.strip().lower()
if n == "":
continue
if n not in freq:
freq[n] = 0
freq[n] += 1
duplicates = []
for w in freq:
if freq[w] >= 2:
duplicates.append(w)
duplicates.sort()
return freq, duplicates
sample = ["API", "db", "api", "cache", "DB", "api", ""]
freq, dup = analyze_words(sample)
print(freq) # {'api': 3, 'db': 2, 'cache': 1}
print(dup) # ['api', 'db']use std::collections::HashMap;
fn main() {
let sample = vec!["API", "db", "api", "cache", "DB", "api", ""];
let mut freq: HashMap<String, i32> = HashMap::new();
for w in sample {
let n = w.trim().to_lowercase();
if n.is_empty() {
continue;
}
*freq.entry(n).or_insert(0) += 1;
}
let mut dup: Vec<String> = Vec::new();
for (k, v) in &freq {
if *v >= 2 {
dup.push(k.clone());
}
}
dup.sort();
println!("{:?}", freq);
println!("{:?}", dup);
}맵/셋 빈도 패턴 결과 해시 충돌 징후 확인
정규화 후 카운팅하면 같은 의미의 키를 하나로 합칠 수 있습니다.
중복 조건은 c >= 2 같은 정책으로 명확히 분리합니다.
이 구조는 데이터 정제 단계와 통계 단계를 자연스럽게 분리해 유지보수가 쉽습니다.
- 평균 시간복잡도:
O(N) - 최악 시간복잡도:
O(N)(해시 충돌 가정 제외) - 공간복잡도:
O(U)(U는 고유 키 수)
Top-K 빈도 추출
문제 의도: 전체 정렬 대신 힙을 사용해 Top-K를 효율적으로 추출합니다.
입력 예시: values=[1,1,1,2,2,3,3,3,3], k=2
출력 예시: 빈도 상위 2개 값
push 후 크기가 k를 넘으면 pop으로 가장 작은 후보를 버려 상위 K만 유지합니다.
#include <algorithm>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;
vector<pair<int, int>> topKFrequent(const vector<int>& values, int k) {
unordered_map<int, int> freq;
for (int v : values) freq[v]++;
using Node = pair<int, int>; // (count, key)
priority_queue<Node, vector<Node>, greater<Node>> pq;
for (const auto& kv : freq) {
int cnt = kv.second;
int key = kv.first;
pq.push({cnt, key});
if (static_cast<int>(pq.size()) > k) pq.pop();
}
vector<pair<int, int>> out;
while (!pq.empty()) {
int cnt = pq.top().first;
int key = pq.top().second;
pq.pop();
out.push_back({key, cnt});
}
sort(out.begin(), out.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
return a.second > b.second;
});
return out;
}
int main() {
auto out = topKFrequent({1, 1, 1, 2, 2, 3, 3, 3, 3, 4}, 2);
for (auto& [k, c] : out) cout << "(" << k << ", " << c << ") ";
cout << "\n";
return 0;
}import java.util.*;
public class Main {
static List<int[]> topKFrequent(int[] values, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int v : values) freq.put(v, freq.getOrDefault(v, 0) + 1);
PriorityQueue<int[]> heap = new PriorityQueue<>(
new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
return Integer.compare(a[0], b[0]);
}
}
); // [cnt, key]
for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
heap.offer(new int[]{e.getValue(), e.getKey()});
if (heap.size() > k) heap.poll();
}
List<int[]> out = new ArrayList<>();
while (!heap.isEmpty()) {
int[] cur = heap.poll();
out.add(new int[]{cur[1], cur[0]}); // [key, cnt]
}
out.sort(
new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
return Integer.compare(b[1], a[1]);
}
}
);
return out;
}
public static void main(String[] args) {
List<int[]> out = topKFrequent(new int[]{1,1,1,2,2,3,3,3,3,4}, 2);
for (int[] p : out) System.out.print("(" + p[0] + ", " + p[1] + ") ");
System.out.println();
}
}import heapq
def top_k_frequent(values, k):
freq = {}
for value in values:
if value not in freq:
freq[value] = 0
freq[value] += 1
# (빈도, 키)로 최소 힙 유지
heap = []
for key, cnt in freq.items():
if len(heap) < k:
heapq.heappush(heap, (cnt, key))
else:
if cnt > heap[0][0]:
heapq.heapreplace(heap, (cnt, key))
out = []
while heap:
cnt, key = heapq.heappop(heap)
out.append((key, cnt))
out.reverse()
return out
print(top_k_frequent([1,1,1,2,2,3,3,3,3,4], 2))
# [(3, 4), (1, 3)]use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap};
fn top_k_frequent(values: &[i32], k: usize) -> Vec<(i32, i32)> {
let mut freq: HashMap<i32, i32> = HashMap::new();
for &v in values {
*freq.entry(v).or_insert(0) += 1;
}
let mut heap: BinaryHeap<Reverse<(i32, i32)>> = BinaryHeap::new(); // (cnt, key)
for (&key, &cnt) in &freq {
heap.push(Reverse((cnt, key)));
if heap.len() > k {
heap.pop();
}
}
let mut out = Vec::new();
while let Some(Reverse((cnt, key))) = heap.pop() {
out.push((key, cnt));
}
out.reverse();
out
}
fn main() {
println!("{:?}", top_k_frequent(&[1, 1, 1, 2, 2, 3, 3, 3, 3, 4], 2));
}맵/셋 빈도 패턴 결과 버킷 상태 추적
빈도 맵을 우선 만든 뒤 최소 힙으로 상위 K만 유지하면 메모리 사용을 줄일 수 있습니다.
전체 정렬은 U log U지만, 힙 유지 방식은 U log K로 개선됩니다.
K가 작을수록 효과가 커집니다.
- 평균 시간복잡도:
O(N + U log K) - 최악 시간복잡도:
O(N + U log K) - 공간복잡도:
O(U + K)
두 문자열 아나그램 판정
문제 의도: 문자 빈도 벡터/맵 비교로 아나그램 판정을 안정적으로 수행합니다.
입력 예시: ("listen", "silent"), ("rat", "car")
출력 예시: true, false
#include <array>
#include <cctype>
#include <iostream>
#include <string>
using namespace std;
bool isAnagram(const string& a, const string& b) {
array<int, 26> cntA{}, cntB{};
for (char ch : a) {
if (isalpha(static_cast<unsigned char>(ch))) cntA[tolower(ch) - 'a']++;
}
for (char ch : b) {
if (isalpha(static_cast<unsigned char>(ch))) cntB[tolower(ch) - 'a']++;
}
return cntA == cntB;
}
int main() {
cout << boolalpha << isAnagram("Listen", "Silent") << "\n";
cout << boolalpha << isAnagram("Dormitory", "Dirty room") << "\n";
cout << boolalpha << isAnagram("abc", "abd") << "\n";
return 0;
}public class Main {
static boolean isAnagram(String a, String b) {
int[] cntA = new int[26];
int[] cntB = new int[26];
for (char ch : a.toCharArray()) {
if (Character.isLetter(ch)) cntA[Character.toLowerCase(ch) - 'a']++;
}
for (char ch : b.toCharArray()) {
if (Character.isLetter(ch)) cntB[Character.toLowerCase(ch) - 'a']++;
}
for (int i = 0; i < 26; i++) {
if (cntA[i] != cntB[i]) return false;
}
return true;
}
public static void main(String[] args) {
System.out.println(isAnagram("Listen", "Silent"));
System.out.println(isAnagram("Dormitory", "Dirty room"));
System.out.println(isAnagram("abc", "abd"));
}
}
def is_anagram(a, b):
cnt_a = [0] * 26
cnt_b = [0] * 26
for ch in a:
if ch.isalpha():
idx = ord(ch.lower()) - ord("a")
cnt_a[idx] += 1
for ch in b:
if ch.isalpha():
idx = ord(ch.lower()) - ord("a")
cnt_b[idx] += 1
return cnt_a == cnt_b
print(is_anagram("Listen", "Silent")) # True
print(is_anagram("Dormitory", "Dirty room")) # True
print(is_anagram("abc", "abd")) # Falsefn is_anagram(a: &str, b: &str) -> bool {
let mut cnt_a = [0i32; 26];
let mut cnt_b = [0i32; 26];
for ch in a.chars() {
if ch.is_ascii_alphabetic() {
let idx = ch.to_ascii_lowercase() as usize - 'a' as usize;
cnt_a[idx] += 1;
}
}
for ch in b.chars() {
if ch.is_ascii_alphabetic() {
let idx = ch.to_ascii_lowercase() as usize - 'a' as usize;
cnt_b[idx] += 1;
}
}
cnt_a == cnt_b
}
fn main() {
println!("{}", is_anagram("Listen", "Silent"));
println!("{}", is_anagram("Dormitory", "Dirty room"));
println!("{}", is_anagram("abc", "abd"));
}맵/셋 빈도 패턴 결과 해시 접근 재확인
아나그램 문제는 같은 멀티셋인가를 묻는 전형적인 빈도 패턴입니다.
정규화 규칙(공백/대소문자 제거)을 우선 확정해야 오답을 줄일 수 있습니다.
비교는 맵 동등성으로 끝나므로 구현이 간결합니다.
- 시간복잡도:
O(N + M)(N,M은 두 문자열 길이) - 공간복잡도:
O(U)(U는 고유 문자 수)
빈도 집계 접근 적용 기준
맵/셋 패턴이 적합한 신호입니다.
- 등장 횟수/중복 여부를 빠르게 판단해야 한다
- 데이터 순회는 가능하지만 매번 정렬은 부담스럽다
- 키 단위 집계 결과를 즉시 저장해야 한다
- 정책 변경(중복 기준, 필터 조건)이 자주 발생한다
이 신호가 보이면 우선 키 설계부터 고정합니다.
빈도 패턴 도입 비용 균형점
패턴 적용 시 고려해야 할 균형점입니다.
- 장점: 한 번 순회로 다수 통계 처리 가능
- 단점: 키 정규화 누락 시 결과 신뢰도 급락
- 장점: 확장성이 높음
- 단점: 고유 키 수가 매우 크면 메모리 부담 증가
속도만 보고 적용하면 데이터 품질 이슈를 놓칠 수 있습니다.
실무 확장 패턴
빈도 기반 패턴은 다음 확장으로 자주 이어집니다.
- 시간 구간별 집계(분/시간/일 단위 버킷)
- 사용자별 상위 행동 패턴 추출
- 오류 코드 Top-K와 알림 임계치 연동
- 중복 요청 탐지(멱등 키 검증)
중요한 기준은 맵/셋 기본 구조를 유지하면서 키 스키마만 확장하는 것입니다.
메모리 제약 대응
고유 키 수가 매우 큰 환경에서는 다음 전략을 검토합니다.
- 윈도우 집계: 오래된 키를 주기적으로 제거
- 근사 집계: Count-Min Sketch 같은 확률 구조 도입
- 샤딩: 키 공간을 분할해 메모리 압력을 분산
- 외부 저장소 오프로딩: 핫 데이터만 메모리에 유지
정확도와 메모리 사용량 사이의 균형을 서비스 요구에 맞춰 조정해야 합니다.
빈도 집계 운영 모니터링 지표
패턴 적용 후에는 아래 지표를 모니터링하는 것이 좋습니다.
- 고유 키 수(
U) 증가 추세 - 특정 키 편중도(최대 빈도/평균 빈도 비율)
- Top-K 결과 변동 폭
- 정규화 실패율(원본 대비 통합 비율)
지표가 없으면 성능 악화와 데이터 품질 저하를 뒤늦게 발견하게 됩니다.
요약 해석
빈도 패턴의 성능은 맵/셋 선택보다 키 설계 품질에 더 크게 좌우됩니다.
정규화와 정책(동점, 중복 기준)을 우선 고정하면 재사용성과 정확도가 함께 올라갑니다.
또한 메모리 상한을 초기에 설정해 두면 운영 중 급격한 비용 증가를 방지할 수 있습니다.
서비스 규모가 커질수록 이 초기 기준의 가치가 더 커집니다.
키 정규화 반례와 복구 절차
실전에서 자주 나오는 반례입니다.
- 대소문자/공백/기호 정규화를 생략해 같은 항목이 분리됨
None, 빈 문자열, 결측값 처리 규칙 누락- Top-K에서 동점 처리 규칙 미정의
- 스트림 입력에서 무한 누적 맵으로 메모리 급증
정책을 코드 주석이 아니라 함수 인자로 명시하면 이런 오류를 줄일 수 있습니다.
빈도 패턴 성능 경계 정리
상충 지점 판단 시에는 평균 성능뿐 아니라 최악 입력 분포, 메모리 제약, 구현 복잡도를 함께 비교해야 합니다.
| 작업 | 평균 시간 | 최악 시간 | 공간 |
|---|---|---|---|
| 카운팅 + 중복 추출 | O(N) | O(N) | O(U) |
| Top-K(힙) | O(N + U log K) | O(N + U log K) | O(U+K) |
| 아나그램 판정 | O(N) | O(N) | O(U) |
복잡도 계산 시 N(입력 크기)와 U(고유 키 수)를 분리해서 보는 것이 중요합니다.
빈도 계산 구간 참고점
- 키 정규화 규칙을 문서와 코드에서 동일하게 유지해야 합니다.
- 해시 기반 구조는 최악 충돌 입력에서 성능이 나빠질 수 있습니다.
- 메모리 예산이 작은 환경에서는 윈도우 집계나 배치 집계를 검토해야 합니다.
- 분석 결과를 출력할 때 정렬 기준을 고정해야 재현성이 높아집니다.
빈도 로직 품질 체크포인트
- 키 정규화 규칙(대소문자/공백/기호)을 코드에 반영했는가
N과U를 분리해 복잡도를 계산했는가- Top-K 동점 처리 정책을 명확히 정했는가
- 스트림 입력에서 메모리 상한 전략을 준비했는가
빈도 패턴 적용 정리
맵과 셋은 빈도 기반 문제를 선형 시간으로 바꾸는 핵심 도구입니다.
키 설계와 정규화 정책을 우선 고정하면, 다양한 집계 문제를 안정적으로 재사용할 수 있습니다.