쉬움
Valid Anagram
코드 라인과 단계 ID를 동기화하고, 변수/포인터/배열·행렬·그래프 엔티티의 상태 스냅샷을 단계마다 갱신한다.
입력
1함수 애너그램인가(s, t):2 만약 길이(s) ≠ 길이(t): 반환 거짓3 개수 = {}4 반복 c in s: 개수[c] += 15 반복 c in t:6 개수[c] -= 17 만약 개수[c] < 0: 반환 거짓8 반환 참
변수
- 단계
- 세기
- i
- 0
- 문자
- a
- 개수
- 1
1 / 15s의 'a' 을(를) 셉니다.
문자 빈도를 세어 두고 상대 문자열로 하나씩 빼, 어긋나면 애너그램이 아니다.
왜 헷갈리는가
'둘 다 정렬해서 비교'해도 되지만 O(n log n)이다. 빈도 세기는 O(n)이고, 무엇보다 '어느 글자에서 어긋났는지'를 보여 준다. 대소문자·유니코드·공백 처리를 문제 정의에서 정해야 한다.
핵심 아이디어
애너그램은 '같은 글자를 같은 개수로' 가진다. s로 카운트를 채우고 t로 빼면, 완벽히 상쇄될 때만 애너그램이다. 도중에 음수가 나오면 t에 더 많은 글자가 있다는 뜻.
복잡도
시간 O(n)·공간 O(k)(글자 종류 수). 정렬 비교(O(n log n))보다 빠르다.
실무에서 어디에 쓰나
'빈도 벡터로 두 집합이 같은지' 판단하는 패턴은 검색·중복탐지에 널리 쓰인다.
- 검색: 철자 순서 무관 매칭(애너그램 그룹핑, 오타 후보)
- 중복 탐지: 필드 순서와 무관한 레코드 동일성(멀티셋 비교)
- 자연어: 단어 빈도(bag-of-words) 벡터 비교의 축소판
- 보안: 문자 분포로 난독화/치환 탐지
흔한 실수
길이 먼저 비교 안 하기(빠른 탈출을 놓침). 유니코드/대소문자 정규화 누락.
기억할 것
- 빈도가 같으면 애너그램.
- 정렬 비교보다 O(n)이 빠르다.
- 길이 먼저 확인해 조기 탈출.
- bag-of-words 비교의 축소판.