값이 몇 번 나오는지를 객체나 Map에 모아 두고 비교하는 풀이 패턴. 배열이나 문자열끼리 비교할 때 생기기 쉬운 중첩 반복 O(n²)을 O(n)으로 줄인다.
// 두 문자열이 같은 글자들로 이루어졌는가(애너그램, Anagram)
function isAnagram(a: string, b: string) {
if (a.length !== b.length) return false
const count = new Map<string, number>()
for (const ch of a) count.set(ch, (count.get(ch) ?? 0) + 1)
for (const ch of b) {
const n = count.get(ch)
if (!n) return false // 없거나 이미 다 썼다
count.set(ch, n - 1)
}
return true
}- 한쪽으로만 빈도표를 만들고 다른 쪽을 순회하며 깎아 나가면 표를 하나만 써도 된다
- 길이를 먼저 비교하면 깎은 뒤 남은 값을 다시 확인할 필요가 없다
- 원리는 해시 테이블의 평균
O(1)조회다. 배열의indexOf로 찾으면 다시O(n²)이 된다 - 실무에서도 같은 생각을 자주 쓴다. 목록을 id로 묶어 두고 조회하거나, 중복을
Set으로 거른다(빅오 표기법, 파이썬 기본 컬렉션)
다른 패턴은 알고리즘 문제 풀이 접근법.